외판원순회.md

비트마스크와 dp를 활용한 외판원 순회 알고리즘이다.

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

import java.util.*;

public class boj2098{
    static Scanner sc = new Scanner(System.in);
    static int[][] map;
    static int[][] dp;
    static int n;
    static int INF = 9999999;
    static int min(int a, int b){
        return (a<b) ? a : b;
    }
    /*
    외판원 순회 (비트마스크 dp DFS)
    loot = 방문한 정점을 1로, 방문하지 않은 정점을 0으로 표현한 2진수
    loot 0으로 남아있는 정점 찾아서 싹 탐색해주면 됨.
    */
    
    static int DFS(int x, int loot){
        if(loot == (1<<n) - 1) return ((map[x][0] != 0) ? map[x][0] : INF);
        if(dp[x][loot] != -1) return dp[x][loot];
        else dp[x][loot] = INF;
        for(int i = 0; i < n; i++){
            if((loot & (1<<i)) == 0 && map[x][i] != 0){
                int tmp = DFS(i, loot | (1<<i));
                dp[x][loot] = min(dp[x][loot], map[x][i] + tmp);
            }
        }
        return dp[x][loot];
    }
    public static void main(String[] args){
        n = sc.nextInt();
        map = new int[n][n];
        dp = new int[n][(1<<n)];
        int res = INF;
        for (int i = 0; i < n; i++) Arrays.fill(dp[i], -1);
        for (int i = 0; i < n; i++){
            for (int j = 0; j < n; j++){
                map[i][j] = sc.nextInt();
            }
        }
        System.out.println(DFS(0, 1));
    }
}