BOJ (Java) 2098번: 외판원 순회

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

---

풀이

완전 탐색의 방법으로 시도하려 했으나, 이 경우 탐색해야 할 노드의 수가 많아져 시간 초과가 발생한다.

알고리즘을 보니 비트마스킹과 DP가 있어 바로 풀이를 봤다.

유명한 알고리즘이었으나 접근 방법이 생소해서 모르면 못 풀겠다 싶었다.

 

[알고리즘] 외판원 순회 문제

 

---

Java 코드

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

public class Main {

    private static final int INF = 16_000_000;
    private static int N;
    private static int end;
    private static int[][] money;
    private static int[][] dp;

    public static void main(String[] args) throws IOException {
        // input
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(bf.readLine());

        money = new int[N][N];
        dp = new int[N][1 << N]; // N 개의 도시를 비트 마스킹으로 표시하기 위해
        end = (1 << N) - 1;

        // 도시 간 거리 입력 저장
        for (int i = 0; i < N; i++) {
            String[] inputs = bf.readLine().split(" ");
            for (int j = 0; j < N; j++) {
                money[i][j] = Integer.parseInt(inputs[j]);
            }
        }

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

    private static int tsp(int now, int visited) {
        // 모든 도시를 다 돌았을 때
        if (visited == end) {
            
            // 현재 노드 (마지막에 방문한)에서 시작점을 갈 수 있다면 해당 값 반환
            if (money[now][0] > 0) {
                return money[now][0];
            }
            return INF;
        }

        // 방문했다면 저장한 값 반환, 아니라면 INF로 초기화 (최솟값 비교를 위해)
        if (dp[now][visited] != 0) {
            return dp[now][visited];
        } else {
            dp[now][visited] = INF;
        }
        
        // 갈 수 있는 모든 노드를 탐색, 최솟값을 찾음 
        for (int i = 0; i < N; i++) {
            if (money[now][i] == 0) continue;
            if ((visited & (1 << i)) != 0) continue;

            int tmp = tsp(i, visited | 1 << i);
            dp[now][visited] = Math.min(dp[now][visited], money[now][i] + tmp);
        }
        return dp[now][visited];
    }
}