[백준] 2098. 외판원 순회

문제 링크

[백준] 2098. 외판원 순회

풀이 과정

비트마스킹과 다이내믹 프로그래밍을 활용해 문제를 풀었습니다.

입력 예)
4
0 10 15 20
5 0 9 10
6 13 0 12
8 8 9 0

각 노드 정점들은 하나의 비트를 차지하게 됩니다. 위 예시에서 정점은 0, 1, 2, 3 총 네 개가 존재하며, 각 정점들은 아래 그림과 같이 하나의 비트 공간을 차지합니다.

위의 비트마스킹을 활용해, 10진수 정수를 인자로 전달하고, 이를 통해 어떤 정점들이 방문되었는지를 표기할 수 있습니다.

static int[][] dp;

public static void main(String[] args) {
    ...

    dp = new int[N][1 << N];
    for (int i = 0; i < N; i++) Arrays.fill(dp[i], INF);
		
    ...
}

2차원 배열 dp[i][j] 는 j 로 표기된 정점들을 지나 정점 i 에 도착했을 때의 최소 비용을 의미합니다. 각 정점들에 대해 비트 공간을 마련해주어야 하기 때문에, 배열의 크기는 N x 1 « N 이 됩니다.

static int TSP(int now, int visit) {
    if (dp[now][visit] != INF) return dp[now][visit];
    if (visit == (1 << N) - 1) return W[now][0] == 0 ? INF : W[now][0];

    int min = INF;

    for (int next = 0; next < N; next++) {
        if ((visit & (1 << next)) != 0 || W[now][next] == 0) continue;

        min = Math.min(min, W[now][next] + TSP(next, visit | (1 << next)));
    }

    return dp[now][visit] = min;
}

TSP 메소드는 인자로 두 개의 정수를 받습니다. 첫 번째 인자로는 현재 방문한 정점 번호를, 두 번째 인자는 현재 방문한 정점을 포함해 이전에 방문했던 정점들을 표시한 값을 의미합니다. 예를 들어, TSP(2, 13) 은 현재 호출에서 2번 정점을 방문했으며, 13(10)은 1101(2) 이므로, 2번 정점을 포함해 0번, 3번 정점도 이미 방문을 완료한 상태를 의미합니다.

TSP 메소드는 다음의 두 조건에 해당하면 더이상 재귀 함수를 호출하지 않고 반환하게 됩니다.

• 이전에 메모이제이션을 통해 배열 dp의 요소가 갱신되었다면, 해당 값을 바로 리턴합니다.
• 모든 정점을 다 방문했다면, 마지막 정점에서 초기 정점으로 돌아가는 비용을 리턴합니다.

위 조건에 해당하지 않는다면, 연결되고 방문하지 않은 다음 정점들에 대하여, 해당 정점까지의 비용 W[now][next] 에 TSP 메소드를 통해 얻은 나머지 경로에 대한 비용을 더해 최소값을 dp[now][visit] 에 저장하고, 그 값을 리턴합니다.

코드

import java.util.Arrays;
import java.util.Scanner;

public class Main {
    static int N;
    static int[][] W;
    static int[][] dp;
    static final int INF = 987654321;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        N = sc.nextInt();
        W = new int[N][N];
        dp = new int[N][1 << N];

        for (int i = 0; i < N; i++) Arrays.fill(dp[i], INF);

        for (int i = 0; i < N; i++)
            for (int j = 0; j < N; j++)
                W[i][j] = sc.nextInt();

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

    static int TSP(int now, int visit) {
        if (dp[now][visit] != INF) return dp[now][visit];
        if (visit == (1 << N) - 1) {
            return W[now][0] == 0 ? INF : W[now][0];
        }

        int min = INF;

        for (int next = 0; next < N; next++) {
            if ((visit & (1 << next)) != 0 || W[now][next] == 0) continue;

            min = Math.min(min, W[now][next] + TSP(next, visit | (1 << next)));
        }

        return dp[now][visit] = min;
    }
}