[백준] 10971번 외판원 순회 자바

문제 

 

10971번: 외판원 순회 2

 

 

문제 풀이

 

전체 도시를 순회하는 경우, 어느 도시에서 출발하든지 최소비용이 동일하다는 사실을 이해하면 순열을 이용하여 모든 탐색에 한하여 최소비용을 구하면 된다.

 

예를 들어, 3번 도시에서 출발하여 다음과 같은 순서로 순회했을 때가 최소 비용이라고 해보자.

 3 → 2 → 0 → 1 → 3

 

이 순서는 어떠한 시작점으로 바꿔도 위와 같은 최소비용이 나온다.

ex)  2 → 0 → 1 → 3 → 2

ex)  0 → 1 → 3 → 2 → 0

 

이렇게! 따라서 해당 시작점에서의 최소 비용은 시작점을 바꾸면 똑같이 표현이 가능하다.

그래서 시작점과 끝점을 제외한 나머지 N-1개의 순열값을 이용하여 최소 비용을 계속 갱신해주어 답을 구했다.

아 그리고 오류가 났었는데 구한 순서의 값이 길이 없는 경우가 있어서 그 경우를 처리해주면 된다.

 

소스 코드

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class b_10971 {

	static int min = Integer.MAX_VALUE;
	static int N;
	static int[][] w;
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		N = Integer.parseInt(br.readLine());
		w = new int[N][N];
		int[] perm_data = new int[N-1];
		int[] result = new int[N-1];
		boolean[] visited = new boolean[N-1];
		
		for(int i = 0; i < N-1; i++)
			perm_data[i] = i+1;		// 1 ~ N-1 넣기 (0은 시작도시로 임의 설정)
		
		for(int i = 0; i < N; i++) {
			String[] str = br.readLine().split(" ");
			for(int j = 0; j < N; j++)
				w[i][j] = Integer.parseInt(str[j]);
		}
		
		permutation(0, perm_data, visited, result);
		System.out.println(min);
		br.close();
	}
	
	public static void permutation(int depth, int[] data, boolean[] visited, int[] result) {
		if(depth == N-1) {
			solve(result);
			return;
		}
		
		for(int i = 0; i < N-1; i++) {
			if(!visited[i]) {
				result[depth] = data[i];
				visited[i] = true;
				permutation(depth+1, data, visited, result);
				visited[i] = false;
			}
		}
	}
	
	public static void solve(int[] result) {
		int r = 0;	//시작 도시
		int ans = 0;
		
		for(int i = 0; i < N-1; i++) {
			if(w[r][result[i]] == 0)
				return;
			ans += w[r][result[i]];
			r = result[i];
		}
		
		if(w[r][0] == 0)
			return;
		
		ans += w[r][0];
		if(ans < min)
			min = ans;
	}
}