[알고리즘]백준 2098: 외판원 순회(TSP)

외판원 순회(TSP)

---

외판원 순회 문제란 모든 도시를 한 번씩 방문하고 다시 출발점으로 되돌아오는 최소 비용을 구하는 문제이다.

N(도시의 수) 값이 작으면, 순열로도 문제를 해결할 수 있지만 N 값이 매우 커지면 불가능하다. 순열의 시간복잡도가 O(N!)일 때 N의 값이 대략 11을 넘어가면 위험하기 때문이다. N 값이 매우 클 경우, DP를 이용해서 풀어야한다.

 

DP + 비트마스킹

dp[current][visited]: current 도시에서 남은 도시들을 모두 방문하여 출발점으로 되돌아가기 위한 최소비용

• current: current 현재 도시
• visited: 현재까지 방문한 도시들을 비트마스킹으로 표현해놓은 것

 

비트마스킹

모든 도시를 방문한 경우

visited == (1<<N)-1

(1<<N)-1을 통해 모든 비트를 1로 만들 수 있다.

 

도시를 아직 방문하지 않은 경우

visited & (1<<next) == 0

 

도시 방문 표시

visited | (1<<next)

 

로직

1. dp[current][visited]를 INF로 초기화한다.
2. tsp 함수 → 재귀
   • 만약 모든 도시를 방문했다면 current→출발지(0)으로 가는 비용을 return한다. 이때, current→출발지가 불가능한 경우라면, INF return한다.
   • 만약 dp≠INF라면(이미 계산된 경우라면) dp 값을 return한다.
   • dp값을 계산한다. 연결된 도시들을 순회하며 값을 update한다. 이때, 다음 도시는 아직 방문하지 않고, 현재 도시에서 도달할 수 있는 경우여야 한다.

 

문제

 

코드

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

// 152ms
// dp + 비트마스킹
public class Main_2098_G1_TSP2 {
    static final int MAX_NUM = 98765432;
    static int N; // N: 도시의 수
    static int[][] adjMatrix;
    // dp[current][visited]: current에서 출발하여 visited에서 방문하지 않은 도시들을 모두 거쳐
    // 다시 0(출발지)로 되돌아오기 위한 최소비용
    static int[][] dp;

    public static int tsp(int current, int visited){
        // 더이상 방문할 도시가 없다면 return
        if( visited == ((1<<N)-1) ) return adjMatrix[current][0]==0 ? MAX_NUM : adjMatrix[current][0];

        // 이미 계산된 경우라면?
        if( dp[current][visited]!=0 ) return dp[current][visited];

        // 인접한 도시들 방문
        int minVal = MAX_NUM;
        for(int next=0; next<N; next++){
            // current -> next가 불가능한 경우 next
            if(adjMatrix[current][next]==0) continue;
            // 방문했다면 next
            if((visited & (1<<next)) !=0 ) continue;
            minVal = Math.min(minVal, adjMatrix[current][next]+tsp(next,visited | (1<<next)));
        }

        return dp[current][visited] = minVal;
    }

    public static void main(String[] args) throws IOException{
        // 1. 입력 및 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        N = Integer.parseInt(br.readLine());
        adjMatrix = 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++){
                adjMatrix[i][j] = Integer.parseInt(st.nextToken());
            }
        }

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

 

 

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