[BOJ] 2098:외판원 순회

0. 문제

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

2098번: 외판원 순회

 

1. 문제분석

- 외판원 순회(TSP, Traveling Salesman Problem)라는 유명한 알고리즘에 관한 문제이다.

- 그래프 내 각각의 노드의 방문 상태를 알아야 하고 또 이전의 방문 상태 및 현재 방문 노드를 기준으로 다음 방문하는 노드와 상태가 정해진다는 점에서 각 노드의 방문 상태를 나타내기 위한 bitmask와 dynamic programming을 사용해 문제를 풀어야한다. 

 

2. 주의할 점

- 그냥 아무것도 없이 생으로 풀기에는 풀 방법이 잘 떠오르지 않는다. 이런 고전적이고 전형적인 문제들을 통해 특정한 문제 유형에 대한 접근법을 더 빨리 떠올릴 수 있도록 공부하자. 

- Java는 역시 C와 비슷하다. bitmask도 적절히 사용할 수 있도록 공부하자.

- 순회 시작 지점이 어디인지는 중요하지 않다. 어떤 노드(도시)를 고른다고 하더라도, 어쨌든 사이클이 발생하게 되므로(원래 출발 지점으로 돌아오니까) 순회 경로 자체는 동일하다. 따라서 처음부터 시작 지점을 임의로 정하고 문제를 풀어나가는 편이 좋다.

 

3. 소스코드(Java)

// boj 2098 : 외판원 순회 (TSP)
// dp, bitmask

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

public class boj_2098 {

    private static int N;
    private static int visitedAll;
    private static int W[][];

    // dp[i][status] : 현재까지 도시들을 방문한 상태(status)에서 현재 도시 i를 방문할 경우의 최소 거리
    private static int dp[][];

    private static final int START = 0;
    private static final int INF = 16 * 1000000 + 1;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = stoi(st.nextToken());
        visitedAll = (1 << N) - 1;
        W = new int [N][N];
        dp = new int [N][1<<N];
        for (int i = 0; i < N; ++i) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < N; ++j) W[i][j] = stoi(st.nextToken());
        }
        System.out.print(TSP(START, 1));
    }


    private static int TSP(int now, int visited) {
        // 모든 노드를 방문 했다면
        if (visited == visitedAll) {
            if (W[now][START] != 0) return W[now][START]; // 다시 원점으로 돌아올 수 있음
            else return INF; // 다시 원점으로 돌아가지 못함
        }

        // 현재 상태에서 현재 노드를 방문한 적이 있는 지 판단
        int ret = dp[now][visited];
        if (ret > 0) return ret;
        else ret = INF;

        for(int i = 0; i < N; i++) {
            // 도시 i를 방문한 적이 없고, 현재 위치에서 i로 갈 수 있다면 이동
            if((visited & (1<<i)) == 0 && W[now][i] > 0) {
                ret = Math.min(ret, TSP(i, visited|(1<<i)) + W[now][i]);
            }
        }
        return dp[now][visited] = ret;

    }
    private static int stoi(String s) {return Integer.parseInt(s);}
}

4. 여담

- 워낙 유명한 문제라... 참고할 자료가 많음..