[백준] 2098번 : 외판원 순회

2098번: 외판원 순회

---

[비트마스킹 + DP]

처음에 문제를 보고 최소 스패닝 트리 문제인 줄 알았다. 그래서 크루스칼 알고리즘을 사용해서 풀 수 있겠다 싶었지만, 최소 스패닝 트리와 완전히 달랐다. 최소 스패닝 트리는 한 정점이 2개 이상의 간선을 가질 수 있지만, 외판원 순회의 경우 한 정점은 2개만 갖을 수 있다. 그리고 반드시 출발점 -> ... -> 출발점이 되어야한다. 이때의 최소값을 구하는 문제였던 것이다.

 

DP와 DFS에 취약한 내 단점을 적나라하게 드러낸 문제였던 것 같다. 그래서 이 문제를 통해 많이 배웠고 외판원 순회라는 것을 공부하는 계기가 되었다.

 

외판원 순회(TSM)의 구조는 개인적인 생각으로 DP + DFS와 상당히 유사한 것 같다. 다만 비트마스킹을 사용했다는 점.

 

+추가)

실제로 외판원 순회 문제의 경우 어느 정점에서 출발해도 그 결과값은 동일하다. 예를 들어 6개의 정점이 있을 때

1 - 2 - 3 - 4 - 5 - 6 - 1의 순서로 최소값을 갖는다고 할 때, 2 - 3 - 4 - 5 - 6 - 1 - 2도 동일한 값을 갖는다.

 

#풀이 요약

> 사전 준비 : 인접 행렬 또는 인접 리스트, 각 정점이 방문한 정점에 따라 갖는 배열 dp[][] = new int[ n ][ (1 << n) ]

 

0. if(dp[현재 정점][방문해온 정점의 정보] != 0) return dp[current][visit]

1. tmp = INF

2. 현재 정점의 인접한 정점 중 방문하지 않았거나 거리가 0이 아닌 곳 탐색하여 result에 저장 (재귀로 반복)

3. result가 tmp보다 작다면 tmp = result로 갱신

4. 모든 정점을 방문했는지?

4-1. 출발점으로 돌아갈 수 있는가? return 출발점으로 가는 길의 거리

4-2. 출발점으로 갈 수 없는가? return INF

 

코드와 주석을 함께 보면 조금 더 이해가 갈 것 같다.

# Code </>

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

public class Main2 {

    static final int INF = 1000000000;
    static int[][] map = new int[16][16];
    static int[][] dp = new int[16][1 << 16];
    static int n;

    static int TSM(int current, int visit){

        if(dp[current][visit] != 0)
            return dp[current][visit];

        if(visit == (1 << n) - 1){ //모든 정점을 방문하여서 다시 출발점으로 돌아가야 할 때
            if(map[current][0] == 0) //현재 정점에서 출발점으로 못간다면
                return INF;
            else
                return map[current][0]; //현재 정점에서 출발점으로 갈 수 있다면
        }

        int tmp = INF;

        for(int i=0; i<n; i++){
            if((visit & (1 << i)) != 0 || map[current][i] == 0) continue; //이미 다음 정점을 방문했거나, 다음 정점으로의 길이 없다면 skip

            int result = map[current][i] + TSM(i, visit | (1 << i)); //현재 -> 다음 정점으로의 길이와 다음 정점에서의 과정 재귀호출

            if(result < tmp) //result가 INF가 아닌 값을 받아왔다면
                tmp = result;
        }

        return dp[current][visit] = tmp;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        n = Integer.parseInt(br.readLine());

        for(int i=0; i<n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++)
                map[i][j] = Integer.parseInt(st.nextToken());
        }

        System.out.println(TSM(0, 1));
    }
}