[백준] 외판원 순회 2098번 (java) 비트마스킹 + dp

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

 

풀이 방법

외판원 문제를 비트마스킹과 DP를 활용해서 풀이하는 문제이다

DP를 2차원 배열로 선언한 후 dp[y][x] = y를 현재 지점 x를 현재 지점을 포함한 방문한 노드의 인덱스를 비트로 변경했을 때 값으로 설정한다.

 

ex 11001(2진수) -> 1, 4, 5번 방문

 

모든 지점을 방문했을 경우는 (1 << n) -1 이 된다 -> 011111 = 100000 - 1 (2진수)

아래와 같은 코드를 통해 i번 인덱스를 방문했는지 판단한다.

if((visited & (1 << i)) > 0) continue; 

 

이후에는 일반적인 dp문제와 동일하게 풀이하면 된다.

 

import java.io.*;
import java.util.*;


public class Main {

    static int n;
    static int[][] W;
    static int[][] dp;
    static int ans;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        n = Integer.parseInt(br.readLine());
        W = new int[n][n];
        dp = new int[n][1 << n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 0; j < n; j++) {
                W[i][j] = Integer.parseInt(st.nextToken());
            }
            Arrays.fill(dp[i], -1);
        }
        System.out.println(dfs(0, 1));
    }

    static int dfs(int idx, int visited) { // 현재 idx이고 지금까지 방문한 것이 visited이다.
        if (visited == (1 << n) - 1) { //모든 지점 방문했을 때
            if (W[idx][0] == 0) return 987654321;  // 돌아갈 수 없으면 큰 값 반환
            return W[idx][0];
        }
        if(dp[idx][visited] != -1) {
            return dp[idx][visited];
        }
        int ret = 987654321;
        for (int i = 0 ;i < n;i++) {
            if((visited & (1 << i)) > 0) continue;
            if (W[idx][i] == 0) continue;
            ret = Math.min(ret, dfs(i, visited | (1 << i)) + W[idx][i]);
        }
        dp[idx][visited] = ret;
        return ret;
    }
}