TSP(외판원의 순회) 알고리즘

오늘은 문제를 풀다가 TSP(Traveling Salesman problem) 알고리즘을 공부하게 되었습니다.

 

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

 

TSP 알고리즘은 "특정 출발점에서 모든 점을 순회하여 다시 출발점으로 돌아오는 최단 거리"를 구하는 알고리즘입니다. 

 

처음 이 문제에 대해 접근할 때, 각 출발점에 대해 최단 순회 경로를 구하는 것이 당연하다고 생각했었습니다. 

 

하지만 위 그래프를 2차원 배열로 바꿔서 생각해보면, 

 

이런 2차원 형태에서, 순환이 가능한 조합은 위 2차원 배열에 row 당 하나의 체스의 록을 넣을 수 있는 경우와 같습니다. 

예로 1 >2 >3 >5 > 4 >1 의 순환이나 2 > 3 > 5 > 4 > 1 > 2 은 같은 값을 가지게 됩니다. 출발점을 고려하지 않고, 각 row당 column이 겹치지 않게 하나씩 뽑아 주면 최단 순환거리를 구할 수 있습니다. 

 

만일 브루트 포스로 위 경우를 구하게 된다면, 정점이 N인 경우 N! 만큼의 경우를  확인해 줘야 합니다. 문제의 경우 N의 최대 값은 16이며 16! 은 20,922,789,888,000으로 너무 커서 문제에서 정한 시간 안에 해결할 수 없습니다.

 

시간을 줄이기 위해 중복되는 연산 과정을 생략 할 수 있는 DP 알고리즘이 필요합니다. 

 

지금까지 방문한 점에 대해서 값을 저장하고 싶지만, 어떻게 이를 구분하여 저장을 해야 할지가 문제입니다. 

만일 배열을 통해 저장해야 한다먄 1,3번을 방문한 경우 arr = [true, false, true, false, false] 이런 식으로 저장을 해야 하는데 이렇게 저장하는 방법은 메모리를 많이 사용하고, 배열을 검증하는 시간이 필요해집니다.

 

하지만 비트 마스킹을 도입한다면 위 문제를 좀더 쉽게 해결할 수 있습니다. 

 

1번 3번을 방문한 경우를  > 101

1번 3번 5번을 방문한 경우 > 10101

..

 

그렇다먄 정점이 N개 일 때 생길 수 있는 경로의 수는 (N^2)-1가 됩니다. (비트 연산자를 활용한다면 (1 << N)-1으로 표현 가능)

 

만일 현재 1번 3번 방문한 경우, 

 

그다음 정점이 4번인 경우 : 101 | 1000  = 1101 

그다음 정점이 3번인 경우:  101 & 100!= 0 이 성립 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Num2098외판원의순회 {
    static int n,INF=10_000_000;
    static int[][] map;
    static int[][] dp;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        // dp의 의미
        // dp[3][1101] : 현재 노드가 3이고 방문하지 않은 노드가 2번이며 다시 0번 노드로 순회하는 최소 값.
        dp = new int[n][(1<<n)-1];
        for(int i=0;i<n;i++){
            Arrays.fill(dp[i],-1);
        }
        for(int i=0;i<n;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0;j<n;j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        System.out.print( recursion(0,1));
    }
    public static int recursion(int now,int check){
        if(check == (1<<n)-1) {
            // 출발점이 0 이기때문에 0 으로의 값을 더해준다. 
            if(map[now][0] == 0) return INF;
            else return map[now][0];
        }
        // 그 값이 존재하면 리턴
        if(dp[now][check] != -1) return dp[now][check];
        dp[now][check] = INF;

        for(int i=0;i<n;i++){
            if(map[now][i] == 0) continue;
            // 이동된 비트값
            int next =  check | 1 << i;
            // 경로가 없거나, 현재 비트 값과 이동될 비트 값 중 1이 겹치면 x 
            if(map[now][i] ==0 || (check & (1<<i)) != 0) continue;
            dp[now][check] = Math.min(dp[now][check], recursion(i,next) + map[now][i]);
        }
        return dp[now][check];
    }
}

 

참고 : https://loosie.tistory.com/271

[BOJ] 백준 2098번 외판원 순회 (Java)