[백준] 외판원 순회

참고 : www.acmicpc.net/problem/2098

2098번: 외판원 순회

 

 

- dp문제

- 답 보고 풀었다..

- dp + 비트마스크 문제

- ex) n= 4일 때 bit : 1111 (15) 를 모든 정점을 방문했다고 생각

- dp[node][visit] 일 때의 최소값을 구해주면 된다. (for로 모든 노드에서 출발했을 때 dfs로 탐색) 

 

 

import java.io.*;
import java.util.Arrays;
import java.util.Scanner;

public class Solution {
    private static int[][] arr;
    private static int[][] dp;
    private static int N;
    private static int INF = 16 * 1_000_000;

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

        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++) {
                arr[i][j] = sc.nextInt();
            }
        }

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

    private static int tsp(int node, int visit) {
        if(visit == (1<<N) -1) {
            if(arr[node][0] == 0) return INF;
            return arr[node][0];
        }

        // 이미 지나간 노드값이라면 그대로 return
        if(dp[node][visit] != INF) return dp[node][visit];

        for (int i = 0; i < N; i++) {
            int next = visit | (1<<i);

            // 이미 0으로 가는 것이 불가능 하거나
            // visit에 이미 ex) 0011 0010 -> 1 이미 들렀던 곳이거나
            if(arr[node][i] == 0 || (visit & (1<<i)) != 0) continue;

            // dp[node][visit]의 현재 비용 tsp (현재까지 이동하는 비용 ) + 0으로 이동하는 비용
            dp[node][visit] = Math.min(dp[node][visit], tsp(i, next) + arr[node][i]);

        }

        return dp[node][visit];
    }
}