백준 10971-외판원 순회 2; Java

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

10971번: 외판원 순회 2

import java.util.*;
import java.io.*;

public class Main {
	static int N, result;
	static int[][] W;
	static ArrayList<Integer> list;

	//현재 위치, 방문 도시 리스트, 누적 비용 
	public static void tsp(int cur, ArrayList<Integer> list, int cost) {
		//모든 도시를 다 방문 
		if(list.size()==N) {
			int first=list.get(0);
			int last=list.get(list.size()-1);
			if(W[last][first]!=0) {
				cost=cost+W[last][first];
				if(cost<result) {
					result=cost;
				}
			}
			return;
		}
		
		for(int i=0;i<N;i++) {
			if(W[cur][i]!=0 && !list.contains(i)) {
				list.add(i);
				tsp(i, list, cost+W[cur][i]);
				list.remove(list.size()-1);
			}
		}
	}
	
	public static void main(String[] args)throws Exception {
		// TODO Auto-generated method stub
		BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
		N=Integer.parseInt(br.readLine());
		W=new int[N][N];
		list=new ArrayList<Integer>();
		
		for(int i=0;i<N;i++) {
			String line[]=br.readLine().split(" ");
			for(int j=0;j<N;j++) {
				W[i][j]=Integer.parseInt(line[j]);
			}
		}
		result=Integer.MAX_VALUE;
		//시작점이 0
		//모든 점을 다 방문하는 순회이므로 모든 점을 시작점으로 tsp를 계산해주지 않아도 된다.
		list.add(0);
		tsp(0, list, 0);
			
		BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
		bw.write(Integer.toString(result));
		bw.flush(); bw.close();		
	}

}

백준 모든 순열 문제와 비슷하게 풀었다.

for문을 통해 방문하지 않은 정점이면서 길이 있는 정점(도시)를 리스트에 추가하며 dfs해준다.

모든 도시를 방문하면 경로의 비용을 계산하고 비용의 최솟값을 갱신해준다.

 

처음에는 1부터 n까지 모든 정점을 시작점으로 tsp를 계산해봐야 한다고 생각했다.

그런데 tsp는 모든 정점을 방문하고 처음 정점으로 돌아가는 순회이므로 사이클이 만들어진다.

그래서 어떤 한 정점을 선택해 시작점으로 tsp를 하면 모든 경로를 탐색하는 것이다.

이 점이 중요했던 것 같다. 

 

다음으로는 외판원 순회 1을 풀어보려고 한다.