[알고리즘] 외판원 순회 문제

1. 알고리즘 문제 정의

• 외판원 순회 문제는 조합 최적화 문제의 일종으로, NP-난해 집합에 속하기 때문에 계산이론에서 해를 구하기 어려운 문제의 대표적인 사례로 많이 다룬다.
• 외판원 문제는 다음과 같다.

  어떤 외판원이 N개의 도시를 방문할 계획을 수립하고 있다고 가정하자. 각 도시는 다른 모든 도시와 도로로 연결되어 있다. 출장 비용을 최소로 줄이기 위하여 외판원이 거주하고 있는 도시에서 각 도시를 한번씩만 방문하고 다시 출발한 도시로 돌아오는 가장 최소 비용의 일주여행 경로를 찾고자 한다.

• 외판원 순회 문제의 최적해는 동적 계획법으로 지수 시간에 풀수 있다. 구현은 아래 참조.

2. 구현

• 백준 10971번 외판원 순회2

  동적 계획법 + 비트마스킹으로 풀이가 가능하다.
  DFS(int cur, int visited) : 방문 상태가 visited이고, 현재 cur위치일 때, 시작 위치까지 최소 거리

• 소스 코드

public class Main {
	public static BufferedReader br;
    public static BufferedWriter bw;
    public static int N, INF = 987654321;
    public static int[][] adj = new int[10][10];
    public static int[][] dp = new dp[10][1024];
    
    public static int dfs(int cur, int visited) {
    	//기저조건 : 모든 도시를 방문하고 다시 0으로 가는 경우가 있을 경우 거리 리턴
        if (visited == (1 << N) - 1) {
        	if (adj[cur][0] == 0) return INF;
            else return adj[cur][0];
        }
        
        if (dp[cur][visited] != INF) return dp[cur][visited];
        
        for (int i = 0; i < N; i++) {
        	if (adj[cur][i] == 0 || (visited & (1 << i)) != 0) continue;
            int next = visited | (1 << i);
            dp[cur][visited] = Math.min(dp[cur][visited], dfs(i, next) + adj[cur][i]);
        }
        return dp[cur][visited];
    }
    
    public static void input() throws IOException {
        N = Integer.parseInt(br.readLine());
        for (int i = 0; i < N; i++) {
            String[] in = br.readLine().split(" ");
            Arrays.fill(dp[i], INF);
            for (int j = 0; j < N; j++)
                adj[i][j] = Integer.parseInt(in[j]);
        }
    }

    public static void main(String[] args) throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        input();
        bw.write(dfs(0, 1) + "\n");
        bw.flush();
        bw.close();
    }
}