[10971] 외판원 순회2

문제 : https://www.acmicpc.net/problem/10971

Key Point

go[i][j] = 도시 i에서 도시 j로 가기 위한 비용
어떤 도시를 방문할 지 city[] 라는 배열에 넣는다.
city[0] city[1] … city[N-1] 은 각각 도시1, 도시2, … 도시N-1을 나타냄

Explain

N의 범위 : 2<=N<=10 이므로 모든 경우를 시간 복잡도 안에 구할 수 있다.
모든 도시를 한번만 거친다고 하였므로 순열을 이용해서 풀 수 있다.
N = 4일 경우 순회할 수 있는 경우는 4개이다.

1->2->3->4
2->3->4->1
3->4->1->2
4->1->2->3

문제에서 N개의 도시를 거쳐 다시 시작했던 지점으로 돌아간다고 했으므로
1번 도시를 시작도시로 정해놓고 (N-1)!개의 경우를 구하면 된다.

Code

public class Exam10971 {
	
	// 다음 순열을 구하는 next_permutation() 함수
	public static boolean next_permutation(int[] a) {
		int i = a.length-1;
		while(i>0 && a[i-1]>=a[i]) {
			i--;
		}
		if(i<=0) {
			return false;
		}
		
		int j  = a.length-1;
		while(a[j]<=a[i-1]) {
			j--;
		}
		
		int tmp = a[i-1];
		a[i-1] = a[j];
		a[j] = tmp;
		
		j = a.length-1;
		while(i<j) {
			tmp = a[i];
			a[i] = a[j];
			a[j] = tmp;
			i++;
			j--;
		}
		return true;
	}

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		int test_case = Integer.parseInt(bf.readLine());
		int[][] cost = new int[test_case][test_case];
		// i에서 j로 가기 위한 비용
		
		for(int i=0;i<test_case;i++) {
			for(int j=0;j<test_case;j++) {
				StringTokenizer st = new StringTokenizer(bf.readLine(), " ");
				cost[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int[] city = new int[test_case];
		for(int i=0;i<test_case;i++) {
			city[i] = i; // 도시를 의미
		}
		
		int ans = Integer.MAX_VALUE;
		
		do {
			boolean possible = true;
			int sum = 0;
			for(int i=0;i<test_case-1;i++) {
				if(cost[city[i]][city[i+1]] == 0) {
					possible = false;
				}else {
					sum += cost[city[i]][city[i+1]];
				}
			}
			
			if(possible == true && cost[city[test_case-1]][city[0]] !=0) {
				// 다음 도시로 갈 수 있고, 처음 도시로 돌아갈 수 있다면
				sum+=cost[city[test_case-1]][city[0]];
				if(ans>sum)
					ans = sum;
			}
		}while(next_permutation(city));
		
		System.out.println(ans);
	}

}