외판원 순회(TSP) 알고리즘, 백준 2098번 (Java)

외판원 순회(TPS)는 방향이 있는 그래프에서 시작점부터 출발하여 모든 지역을 중복없이 방문하고 시작점으로 돌아올 때 최소 비용의 거리를 구하는 문제이다.
(이때 시작점은 무엇을 선택하든 최종적으로 사이클을 이루기 때문에 결과가 같다)

그래프의 모든 노드를 최소 비용으로 잇는 유명한 알고리즘을 못 쓰는 이유를 설명하자
면

Minimum Spanning Tree

• 방향이 있는 그래프는 구할 수 없다

Topological Sort

• 사이클이 있는 그래프는 구할 수 없다

때문에 외판원 순회는 가능한 경우의 수를 BFS 또는 DFS로 살펴보되, 이미 방문한 경로는 DP를 이용해 중복을 줄일 수 있는데, 이를 위해 BitMasking을 통해 방문 표시를 해준다.

visited 배열 대신 비트마스킹을 사용하는 이유는, 일반적으로 nodeA -> nodeB 로 가는 비용만 DP를 이용해 갱신하면 되는 반면 TPS는 (방문한 노드들) -> nodeB 처럼 노드 도착하기 전에 어떤 노드들을 방문했는지에 따라 비용을 저장해야하고, [도착한 노드] + [이전에 방문한 노드들] 을 작성해야하는데 이전에 방문한 노드들을 visited 배열로 저장하려면 메모리를 너무 크게 잡아먹는다.

간단하게 풀이 아이디어를 떠올리자면
A B C D 노드가 있을 때 방문 기록은 (0000 ~ 1111) 이진법으로 표시할 수 있고

A 에서 출발해서 모든 노드를 방문하고 마지막 도착한 노드가 D라면 총 비용은 DP[D][1111(2)] 에 넣어야하고, 값은
A B C 방문 완료 -> D 방문 일 때 DP[C][1110(2)] + dist[C][D]
A C B 방문 완료 -> D 방문 일 때 DP[B][[1110(2)] + dist[B][D]
중 최소값이다

또한 마지막으로 D -> A 를 더해주는 것을 잊지말자

package gold;

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

// 외판원 순회 (Traveling Salesman problem)
// DFS + DP + Bitmasking
public class No2098 {
    static int N;
    static int[][] map;
    static int[][] dp;
    static int maxBitMask;
    static int ans = Integer.MAX_VALUE/2;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        map = new int[N][N];
        maxBitMask = (int)Math.pow(2,N);
        // 만약 N이 4라면 0000~1111 (2) 이용해서 방문표시
        dp = new int[N][maxBitMask];
        for(int i = 0; i < N; i++){
        // 처음 dp를 모두 INF로 초기화
            Arrays.fill(dp[i],Integer.MAX_VALUE/2);
            st = new StringTokenizer(br.readLine());
            for(int j = 0; j < N; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        dfs(0, 1);
        System.out.println(ans);
    }

//    @param : 현재 방문한 도시, 현재까지 방문한 도시들 (bitmasking)
    public static void dfs(int city, int visited){
//        전부 방문했으면
        if(visited == maxBitMask-1){
//            마지막 노드에서 출발 노드로 돌아오는 엣지가 없으면 오류
            if(map[city][0] == 0){
                return;
            }
            ans = Math.min(ans, dp[city][visited]+map[city][0]);
            return;
        }
        for(int i = 0; i < N; i++){
            if((visited & (1 << i)) == 0 && map[city][i] != 0){
//                System.out.println("현재 방문: "+String.format("%04d",Integer.parseInt(Integer.toBinaryString(visited))));
//                System.out.println("다음 방문: "+String.format("%04d",Integer.parseInt(Integer.toBinaryString(visited | (1 << i)))));
//                System.out.println("-----------");
                //        출발점에서 다음 노드까지 거리 초기화
                if(visited == 1){
//                    System.out.println("초기 값 세팅");
                    dp[i][visited | (1 << i)] = map[0][i];
                    dfs(i, visited | (1 << i));
                }
                // 방문 기록이 동일할 때
                // i까지 가는 비용 vs 현재 비용 + 현재 위치에서 i까지 가는 비용 비교
                else if(dp[i][visited | (1 << i)] > dp[city][visited] + map[city][i]){
                    dp[i][visited | (1 << i)] = dp[city][visited] + map[city][i];
                    dfs(i, visited | (1 << i));
                }
            }
        }
    }
}