[백준] code.plus(브루트포스-순열,JAVA)10971번, 외판원 순회 2

문제 링크

10971번: 외판원 순회 2

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

브루트 포스란.

모든 경우의 수를 대입시켜서 가장 알맞은 경우의 수를 결과로 출력하는 것입니다.

 

순열이란

n개의 원소를 중복없이 나열하는 것입니다.

순열 - 위키백과, 우리 모두의 백과사전

 

이 문제에 핵심은

1. 도시는 1~N 번호가 매겨져 있다.

2. 도시 번호는 중복이 불가능하다. = 순열이다.

3. 순열을 완성한 뒤 순열 첫 값으로 이동하는 비용을 더해야 한다.

 

배열

permutation  : 현재 경우의 순열

 

check : 방문한 도시 확인하는 배열

 

cost : 도시를 이동할 때 지불하는 비용

 

permutation, check, cost와 재귀를 이용하여 모든 경우의 순열을 구하였습니다.

 

문제를 해결할 때에 만들 수 있는 모든 경우의 순열을 만들었습니다.

순열에 들어갈 값을 저장할 때마다 도시 이동 비용을 합하였습니다.

순열이 완성되었을 때 순열에 저장된 첫 도시로 이동하는 비용을 더해주어 비용 최소값을 구합니다.

 

문제에 해결알고리즘은

1. N개 도시 중 첫 번째 순열에 값을 지정하고 해당 check를 true로 바꾸어주었습니다.

2. 순열의 모든 경우의 수를 구하였습니다.

3. 순열의 들어갈 수를 저장할 때마다 지불해야 할 비용을 더해주었습니다.

4. 순열이 완성되었을 때 모든 지불 비용의 합과 순열 마지막 도시에서 첫 도시로 이동하는 비용을 더합니다.

5. 모든 순열을 탐색하여 구한 최소 비용 값을 결과로 출력하였습니다.

 

• BufferedReader를 사용하여 입력 값을 저장하였습니다.
• StringTokenizer를 통해 도시간 이동 비용을 배열에 저장하였습니다.
• 모든 경우의 도시 이동 비용을 구하는 minCost 함수를 만들었습니다.
• BufferedWriter에 최소 도시 비용의 합을 저장하였습니다.
• BufferedWriter에 저장된 값을 출력하였습니다.

• minCost는 cost, permutation, check와 재귀를 사용하여 모든 경우에 도시 이동의 합을 구하였습니다.
• minCost는 순열이 완성되었을 때 마지막 도시에서 처음 도시로 이동하는 비용을 합해서 최소 비용을 구하였습니다.

 

결과 코드

import java.io.*;
import java.util.*;
public class Main{
	public static int N;
	public static int[][] cost;		//도시 이동 비용 저장 배열
	public static int[] permutation;	//현재 순열 저장 배열
	public static boolean[] check;		//도시 방문 확인 배열
	public static int min = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException{
    	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //입력값 처리하는 BufferedReader
    	BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        //결과값 출력하는 BufferedWriter
        //------입력값 저장 및 배열 초기화------
    	N = Integer.parseInt(br.readLine());
    	StringTokenizer st;
    	cost = new int[N][N];
    	check = new boolean[N];
    	permutation = new int[N];
    	for(int i=0;i<N;i++) {
    		st = new StringTokenizer(br.readLine()," ");
    		for(int j=0;j<N;j++) {
    			cost[i][j] = Integer.parseInt(st.nextToken());
    		}
    	}
        //-------첫 출발 도시 탐색-----
    	for(int i=0;i<N;i++) {
    		check[i] = true;
    		permutation[0] = i;
    		minCost(1, 0, i);	//함수 실행
    		check[i] = false;
    	}
    	bw.write(min + "\n");	//최소 비용 BufferedWriter 저장
    	bw.flush();			//결과 출력
    	bw.close();
    	br.close();
    	
    }
    //--------모든 이동 경우 최소 비용 구하는 함수--------
    public static void minCost(int length,int cur, int start) {
    	if(length==N) {
        	//마지막 도시에서 첫 번째 도시 이동하는 비용
    		int temp = cost[permutation[length-1]][start];	
    		if(temp!=0)
    			min = Math.min(min, cur + temp);	//최소값 구하기
    		return;
    	}
      	//방문할 도시 탐색
    	for(int i=0;i<N;i++) {
    		if(!check[i]) {
    			check[i] = true;
    			permutation[length] = i;
    			if(cost[permutation[length-1]][permutation[length]]!=0)	//이동할 수 있으면
    				minCost(length+1, 
                    		cur+cost[permutation[length-1]][permutation[length]],start);
    			check[i] = false;
    		}
    	}
    	return;
    }
}