백준 10971 외판원 순회2 (Java)

1. 문제 링크

10971번: 외판원 순회 2

 

2. 문제 및 입출력예제

 

3. 문제 풀이

외판원 순회 문제로 전형적인 TSP 문제이다.

가장 적은 비용으로 순회를 해야하기 때문에 순열로 방문할 도시의 순서를 정했다.

또한 순회라는 것이 첫 출발점으로 다시 돌아오는 것이기 때문에 시작점은 1번으로 잡고 했다.

 

4. 코드

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

public class Main {
	static int N, map[][], result;
	static boolean[] city;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		map = new int[N][N];
		for(int i=0;i<N;i++) {
			String[] split = br.readLine().split(" ");
			for(int j=0;j<N;j++) {
				map[i][j] = Integer.parseInt(split[j]);
			}
		} 
		
		result = Integer.MAX_VALUE;
		city = new boolean[N];
		city[0] = true;
		dfs(1, 0, 0); //0부터 시작
			
		System.out.println(result);	
	}
	private static void dfs(int cnt, int now, int sum) {
		if(cnt == N) {
			if(map[now][0] == 0) {
				return;
			}
			result = Math.min(result, sum+map[now][0]);
			return;
		}
		for(int i=1;i<N;i++) {
			if(!city[i] && map[now][i]!=0) {
				city[i] = true;
				dfs(cnt+1, i, sum+map[now][i]);
				city[i] = false;
			}
		}
		
	}
}