[JAVA] 외판원 순회 문제 (TSP) + 시간초과 해결방법

외판원 순회 문제(TSP) 란?

• 모든 도시들 간에 이동비용이 주어졌을 때, 각 도시들을 한번만 방문하고 처음 시작점으로 돌아오는 최소 비용을 구하는 문제
• TSP의 핵심 논리는 반복되는 부분을 제거해서 시간복잡도를 줄이는 것
• ex) 0, 1, 2, 3, 4, 5 도시가 있다고 생각해보자
• 모든 도시가 이어져 있을때 모든 경로를 가보려면, 최소 비용을 구하기 위해 (6-1)! = 120개의 경로를 비교해야 함
• 시간복잡도가 n! 식으로 나오면 n이 13정도만 되어도 1초가 넘어감
• 시간을 줄일 수 있는 방법을 생각해보자
• 0->1->2->3->...->0 과 0->2->1->3->...->0 의 상황을 생각해보면
• 0에서 출발해 1,2,3 도시를 거쳤고 현재 3번 도시에 있는 상황
• 이 두 상황에서는 4, 5번 도시를 들려 다시 0으로 돌아오는 작업만 남았는데, 이 작업이 사실 똑같은 작업임
  • 0->1->2->3->4->5->0 이 최소 비용 경로라는 것을 알고 있다면 0->2->1->3 상황에서는 뒤에 도시들을 직접 가보지 않아도 0->2->1->3->4->5->0 이 최소 비용 경로라는 것을 알 수 있음
• 그런데 이 알고리즘을 적용하려면 남은 도시들에 따른 최소 비용이 모두 저장이 되어 있어야 함
• 이를 저장하는 방법으로 2진수 활용
• dist[ i ][ visited ] = 현재 i 도시에 있고, 지금까지 방문한 도시 리스트가 visited 일 때 남은 도시들 방문 후 처음 도시로 돌아가는 최소 비용 저장
• visited는 2진수를 활용해서 만약 0, 1, 4번 도시를 방문했다면 visited = 10011(2) = 19(10)
• n이 커지면(약 27정도) TSP 알고리즘을 사용해도 배열 크기 문제로 사용할 수 없는 방법이지만 모든 경로를 방문해서 구하는 방법보다는 시간이 매우 짧기 때문에 알아두면 좋을듯 함

구현

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

2098번: 외판원 순회

• 이 문제를 TSP를 통해 해결하면서 구현해봄

코드

주의사항 (시간초과 해결방법)

• 모든 도시 방문 후 마지막에 시작도시로 갈 수 없는 경우(cannotCycle)와 방문하지 않은 경우(notVisit)를 분리시켜야 함
• 갈 수 없는 경우에 notVisit을 return 시킨다면 나중에 방문하지 않은 상황으로 판단하여 다시 방문하는 상황 발생 => 시간초과
• cannotCycle의 값은 입력 데이터로 만들어질 수 없을 정도로 큰 값으로 임의 지정
• cannotCycle이 notVisit보다 작아야 함 => cannotCycle이 더 크면 dist에 갱신이 안되기 때문
• notVisit을 int 최대값으로 하면 실행 중 int의 최댓값 넘어가는 상황 발생하기 때문에 cannotCycle보다 더 큰 임의 값으로 지정

import java.util.Arrays;
import java.util.Scanner;

public class p2098 {

    static final int cannotCycle = 17 * 1000000 + 1;
    static final int notVisit = cannotCycle * 2;
    static int n;
    static int[][] in, dist;

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        in = new int[n][n];
        dist = new int[n][ 1 << n ];

        for(int i = 0 ; i < n ; i ++) {
            for(int j = 0 ; j < n ; j ++) {
                // 0이면 갈 수 없음을 의미
                in[i][j] = sc.nextInt();
            }
            // dist 배열 초기화
            Arrays.fill(dist[i], notVisit);
        }

        dist[0][0] = 0;
        System.out.println(tsp(0, 0));
    }

    static int tsp(int now, int visited) {
        // 현재 노드 방문 처리
        visited = visited | (1<<now);

        // 모든 노드를 방문한 경우
        if(visited == (1<<n) - 1) {
            // 마지막 노드(now)에서 처음으로 갈 수 없는 경우
            if(in[now][0] == 0) {
                return cannotCycle;
            }
            // 갈 수 있는 경우 : 마지막 노드(now)에서 0으로 가는 비용 return
            return in[now][0];
        }

        // 전에 최소경로를 구해놓은 경우 : 구해놓은 최소값 return
        if(dist[now][visited] != notVisit) {
            return dist[now][visited];
        }

        for(int next = 0 ; next < n ; next ++) {
            // now에서 next로 갈 수 있는 경우
            if(in[now][next] != 0) {
                // 아직 next를 방문하지 않은 경우
                if( ( visited & (1<<next) ) == 0) {

                    // visited에 해당하는 노드들을 방문하고 현재 now에 있는 상황
                    // 이 상황에서 남은 노드들을 방문하는 최소값이
                    // now에서 next로 간 후 next에서 남은 노드들을 방문하는 최소값보다 크다면 갱신 필요
                    int temp = tsp(next, visited) + in[now][next];

                    if(dist[now][visited] > temp) {
                        dist[now][visited] = temp;
                    }
                }
            }
        }

        return dist[now][visited];
    }
}

참고 반례 => cycle이 완성되지 않는 경로 중복 제거를 하지 않으면 아래 반례에서 시간초과가 발생함

16
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 0 1 1 1 1 1 1 1 1 1 1 1 1 1
0 1 1 0 1 1 1 1 1 1 1 1 1 1 1 1
0 1 1 1 0 1 1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 0 1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 0 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1
0 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1
0 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1
0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0