백준 2098번 - 외판원 순회

문제

백준 2098번 - 외판원 순회

아이디어

• 우선 가장 단순한 방법은 다음과 같이 재귀를 통한 완전 탐색이 있다.

public class BJ_2098 {

    static int n;
    static int[][] w;
    static int min = Integer.MAX_VALUE;
    static boolean[] visit;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        w = new int[n][n];
        visit = new boolean[n];

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

        visit[0] = true;
        dfs(0, 0, 1, 0);

        System.out.println(min);
    }

    private static void dfs(int start, int now, int depth, int cost) {
        if (depth == n) {
            if (w[now][start] != 0) {
                min = Math.min(min, cost + w[now][start]);
            }
            return;
        }

        for (int i = 0; i < n; i++) {

            if (visit[i] || w[now][i] == 0) continue;

            visit[i] = true;
            dfs(start, i, depth + 1, cost + w[now][i]);
            visit[i] = false;
        }
    }
}

• 시작 도시 N개, 다음 도시는 N-1개, 그 다음 도시는 N-2개 ... 이런 식으로 선택 가능하므로 완전 탐색의 시간 복잡도는 N!과 같다. N이 12만 돼도 5억에 가깝기 때문에 시간 초과가 발생한다.
• 효율적으로 해결하기 위해 외판원 순회 문제의 대표적인 알고리즘인 DP와 비트마스킹을 구현해야 한다.
• 우선 사이클의 최소 비용을 구하는 것이기 때문에 시작 도시를 어느 도시로 하든 최소 비용은 같다. 그러므로 모든 도시를 시작 노드로 해서 구할 필요 없이 하나의 도시만 시작 도시로 해서 구할 수 있다. 시작 도시는 0으로 고정한다.
• DP 점화식 DP[i][j]의 의미는 현재 도시 i에서 방문한 도시 집합 j일 때, 남은 도시를 경유하는 데 최소 비용이다.
• 재귀와 비트마스킹을 통해 미방문 도시를 탐색하고 재귀를 빠져나오면서 이동했던 경로들의 비용을 합한 값 중 최솟값을 출력한다.

예상 시간 복잡도

• 예상 시간 복잡도 : O(N^2 x 2^N)

코드 구현

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

public class BJ_2098 {

    static int n;
    static int[][] w;
    static long[][] dp;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

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

        w = new int[n][n];
        dp = new long[n][1 << n];

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

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

    private static long solve(int now, int visited) {

        //N개 도시를 모두 방문한 경우, 시작 도시(0)로 돌아가야 한다.
        //가는 경로가 없으면 무한대 반환
        if (visited == (1 << n) - 1) {
            return w[now][0] == 0 ? Integer.MAX_VALUE : w[now][0];
        }

        //메모이제이션
        if (dp[now][visited] != 0) {
            return dp[now][visited];
        }

        int min = Integer.MAX_VALUE;
        
        for (int i = 0; i < n; i++) {
            
            //AND 연산으로 방문 체크, 이동 가능 여부 체크
            if ((visited & (1 << i)) == 0 && w[now][i] != 0) {

                //OR 연산으로 다음 방문할 도시 확인
                int next = visited | (1 << i);
                min = (int) Math.min(min, solve(i, next) + w[now][i]);

            }
        }

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