BOJ 2098번 외판원 순회 ( DP ) JAVA

BOJ 2098번 외판원 순회 ( DP ) JAVA

---

풀이

dp 와 비트마스킹이 합쳐진 문제였습니다.
visit 배열을 따로 선언하지 않고, 비트마스킹을 이용하여 문제를 풀이하는 것이 첫 번째 포인트였고, 어떤 노드에서 시작하건, 결국 최솟값은 같다는 것을 알아차리는 것이 두번째 포인트였던 것 같습니다.

 

링크

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

 

소스 코드

---

package boj;

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

public class Boj2098 {
    static int[][] a;
    static int[][] dp;
    static final int INF = 16 * 1_000_000;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        a = new int[n][n];
        dp = new int[n][1 << n];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                a[i][j] = sc.nextInt();
            }
        }
        for (int i = 0; i < n; i++) {
            Arrays.fill(dp[i], INF);
        }
        int res = tsp(0, 1, n);
        System.out.println(res);


    }

    // cur 에서의 방문한 곳들이 visit대로인 상태에서, 모두 돌아 나에게까지로 오는 최단거리를 return 한다.
    public static int tsp(int cur, int visit, int n) {
        if (visit == (1 << n) - 1) {
            if (a[cur][0] == 0)
                return INF;
            else
                return a[cur][0];
        }
        if (dp[cur][visit] != INF)
            return dp[cur][visit];
        for (int next = 0; next < n; next++) {
            //
            if ((visit & (1 << next)) == 0 && a[cur][next] != 0) {
                dp[cur][visit] = Math.min(dp[cur][visit], tsp(next, visit | 1 << next, n) + a[cur][next]);
            }
        }
        return dp[cur][visit];


    }
}