[BOJ/Java] 2098 외판원 순회

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	22843	6129	3657	28.573%

문제

 외판원 순회 문제는 영어로 Traveling Salesman problem (TSP) 라고 불리는 문제로 computer science 분야에서 가장 중요하게 취급되는 문제 중 하나이다. 여러 가지 변종 문제가 있으나, 여기서는 가장 일반적인 형태의 문제를 살펴보자.

 1번부터 N번까지 번호가 매겨져 있는 도시들이 있고, 도시들 사이에는 길이 있다. (길이 없을 수도 있다) 이제 한 외판원이 어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로를 계획하려고 한다. 단, 한 번 갔던 도시로는 다시 갈 수 없다. (맨 마지막에 여행을 출발했던 도시로 돌아오는 것은 예외) 이런 여행 경로는 여러 가지가 있을 수 있는데, 가장 적은 비용을 들이는 여행 계획을 세우고자 한다.

 각 도시간에 이동하는데 드는 비용은 행렬 W[i][j]형태로 주어진다. W[i][j]는 도시 i에서 도시 j로 가기 위한 비용을 나타낸다. 비용은 대칭적이지 않다. 즉, W[i][j] 는 W[j][i]와 다를 수 있다. 모든 도시간의 비용은 양의 정수이다. W[i][i]는 항상 0이다. 경우에 따라서 도시 i에서 도시 j로 갈 수 없는 경우도 있으며 이럴 경우 W[i][j]=0이라고 하자.

 N과 비용 행렬이 주어졌을 때, 가장 적은 비용을 들이는 외판원의 순회 여행 경로를 구하는 프로그램을 작성하시오.

입력

 첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j로 가기 위한 비용을 나타낸다.

 항상 순회할 수 있는 경우만 입력으로 주어진다.

출력

 첫째 줄에 외판원의 순회에 필요한 최소 비용을 출력한다.

예제 입력 1 복사

4
0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0

예제 출력 1 복사

35

 

풀이

 결론부터 말하자면 "비트마스킹"과 "다이나믹 프로그래밍"을 혼합한 문제이다. 문제 자체는 단순하다. 전체 마을을 순회한 최솟값을 찾으면 된다. 단, 지났던 마을은 순회 대상에서 포함되지 않는다.

 사실 항상 경로탐색 문제가 나오면 만들게 되는 경로를 ArrayList나 String에 넣어서 비효율적으로 풀었었는데 비트마스킹을 통해서 전체 경로에 대한 저장을 했을 때 장점이 워낙 많은 것 같아 좋은 공부가 된 것 같아서 풀이를 정리해보고자 한다.

 

 일단 해당문제의 경우 start 지점은 아무곳이나 정하면 된다. "모든 마을을 순환"하는 것이 목표이기 때문에 어떤 마을로 시작하건 자기마을로 돌아오게 되고 그 경로는 어떤 마을이 시작점이 되건 상관없다.

 예를 들어 A, B, C 마을이 있다면 A마을을 시작마을로 잡았을 때는

• ABCA
• ACBA

 이고, B마을을 시작마을로 잡았을 때는

• BCAB
• BACB

 인데 두 시작점의 첫번째 경로를 그림으로 그려본다면, 다음과 같이 설정된다.

 ABCA는 1+2+3 = 6이고, BCAB는 2+3+1 = 6으로 결국 모든 마을을 순환한다고 가정했을 때 본인 마을로 돌아오기 때문에 시작점에 대한 걱정은 하지말고 아무마을을 시작점으로 잡으면된다.

 

 

 시작점은 넘어갔으니 이제 모든 순환하는 경로를 만드는 것에 대해서 이야기해보자. 비트마스킹을 구체적으로 어떻게 사용할까? 마찬가지로 A, B, C마을이 있을 때 이 마을들을 배열로 한번 표현해보자.

 아직 아무마을도 방문하지 않았으니 얘는 000으로 표현할 수 있다. 그럼 A마을을 방문하면? 가장 첫마을을 방문했으므로 100이다. (풀이에서는 거꾸로 사용하지만 지금은 일단 설명하기 위해서 역순으로 비트를 나타냈다.)

 이제 이 비트변수 100은 A를 이미 지났던 경로이다. 다음으로 이 경로에서 B마을을 지난다면 110이 될 것이고, C마을을 또 지나면 111이 된다.

 

 이제 모든 마을을 지난 111을 획득하였다. 일단 우린 dfs를 통해서 경로를 만들 것이기 때문에 이 경로가 완료되었는지 안되었는지 확인하는 구문이 반드시 필요하다. 다음 코드를 보자.

if(visited == ((1<<N)-1)){
    if(map[now][0]==0) return;
    int compare = dp[now][visited] + map[now][0];
    answer = Math.min(answer, compare);
    return;
}

 결과 코드 중 검산하는 코드만 발췌한 부분이다. if문을 보면 비트마스킹이 익숙하다면 바로 알아챌 수 있다. 1<<N을 해냈을 때 받을 수 있는 결과는 1000이다. 1을 3만큼 left 이동했기 때문이다. 그럼 이 결과에서 -1을 하면? 우리가 원했던 111 즉, 모든 마을을 1마킹한 값을 받아낼 수 있다.

 

 그럼 이제 거의 끝났다. 마지막으로 순회하던 내용을 저장하는 배열이 필요하다. int[] visited = new int[N<<1];이면 모든 경로를 다 만들 수 있을까? 이 경우는 문제가 생긴다.

 ABCDE 마을이 있다고 했을 때 11110은 ABCD마을은 지나고 E마을은 지나지 않은 경로다. 예를 들어 다음 상황이라고 가정해보자.

1. ABCD > E : ABCD 현재 경로는 5, D>E 값은 15;
2. ACDB > E : ABCD 현재 경로는 10, D>E 값은 1;

 만약에 visited에 이전 경로에 대한 값을 메모하지 않으면 2번 케이스가 분명히 더 최종 결과는 가까울지 몰라도 묻히게 된다. 즉, 이전 도착 마을에 대한 저장 공간이 있어야 구분을 하면서 경로를 찾아내갈 수 있다. 따라서, 정답 코드에서 int[][] dp = new int[N][N<<1];로 공간을 할당해둔 것이다.

 

 마지막으로 경로 검증이다. 다음 경로로 넘어가도 되는지 안되는지를 나타내는 작업이다.

for(int i=0; i<N; i++){
    int next = (1<<i);
    if((visited | next) == visited) continue;
    if(map[now][i] == 0) continue;
    if(dp[now][visited] + map[now][i] < dp[i][visited|next]){
        dp[i][visited|next] = dp[now][visited] + map[now][i];
        dfs(i, visited|next);
    }
}

 next는 다음마을에 대한 비트마스킹이다. 이 next와 기존 visited 경로를 or한 결과가 visited와 같으면 이미 이 경로에 next가 들어있다는 의미이므로 패스한다. 또한 경로에서 현재 마을에서 다음마을에 지나는 경로가 없어도 패스한다.

 이제 내가 만든 경로가 기존에 이 경로를 만들었을 때보다 cost가 적으면 통과하는 If문이다.

 dp[now][visited] + map[now][i] < dp[i][visited|next] : 지금까지의 경로 + 지금마을에서 다음마을cost < 기존에 계산된 다음 마을까지의 경로가 맞으면 dp에 값을 넣고 새로만든 경로로 dfs를 돌린다.

 

 경로를 다 돌렸다면

if(visited == ((1<<N)-1)){
    if(map[now][0]==0) return;
    int compare = dp[now][visited] + map[now][0];
    answer = Math.min(answer, compare);
    return;
}

 에서 최종 마지막으로 다시 첫 시작마을(시작마을을 0으로 지정했었다.)로 돌아올 길이 있는지 없는지 확인하고 비교한다.

 

 결과만 놓고 보았을 때는 그냥 경로를 만들고 최솟값인지 비교만하면 끝이지만 그 과정에서 비트마스킹의 활용도가 중요했던 문제라고 생각한다. 비트마스킹이 의식하고 보지않으면 생각도 안나는 유형이기 때문에 비트마스킹을 사용할 수 있는 문제들은 익혀두고 잊지말고 떠올려서 사용해야할 것 같다.

 

정답 코드

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

public class boj2098 {
    public static int N;
    public static int answer = Integer.MAX_VALUE;
    public static int[][] map, dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        map = new int[N][N];
        dp = new int[N][1<<N];
        for(int i=0; i<N; i++){
            String[] input = br.readLine().split(" ");
            Arrays.fill(dp[i], Integer.MAX_VALUE);
            for(int j=0; j<N; j++){
                map[i][j] = Integer.parseInt(input[j]);
            }
        }
        dp[0][1] = 0;
        dfs(0, 1);
        System.out.println(answer);
    }
    public static void dfs(int now, int visited){
        if(visited == ((1<<N)-1)){
            if(map[now][0]==0) return;
            int compare = dp[now][visited] + map[now][0];
            answer = Math.min(answer, compare);
            return;
        }

        for(int i=0; i<N; i++){
            int next = (1<<i);
            if((visited | next) == visited) continue;
            if(map[now][i] == 0) continue;
            if(dp[now][visited] + map[now][i] < dp[i][visited|next]){
                dp[i][visited|next] = dp[now][visited] + map[now][i];
                dfs(i, visited|next);
            }
        }
    }
}