외판원 문제 자바 - oepan-won munje jaba

백준 2098번: 외판원 순회 [Gold 1]
https://www.acmicpc.net/problem/2098

2098번: 외판원 순회

첫째 줄에 도시의 수 N이 주어진다. (2 ≤ N ≤ 16) 다음 N개의 줄에는 비용 행렬이 주어진다. 각 행렬의 성분은 1,000,000 이하의 양의 정수이며, 갈 수 없는 경우는 0이 주어진다. W[i][j]는 도시 i에서 j

www.acmicpc.net

문제 풀이

• 이 문제는 TSP (Traveling Salesperson Problem) 알고리즘 문제로 그래프의 모든 노드를 한 바퀴 순회하는 최적의 경로를 찾아내는 알고리즘입니다.
• 모든 노드를 순회하는 최적의 경로는 완전 탐색으로도 해결이 가능하지만 노드의 개수가 10개가 넘어간다면 시간 초과에 걸리게 됩니다. 이 문제는 노드의 최대 개수가 16개이기 때문에 Memoization을 적용해야 합니다.

int memo[16][1<<16]; // 현재 노드, 노드 방문 상태

• 문제에는 "어느 한 도시에서 출발해 N개의 도시를 모두 거쳐 다시 원래의 도시로 돌아오는 순회 여행 경로"라고 적혀있기 때문에 각 마을에서 모두 출발해 보면서 경로를 찾아야 할 것 같지만 실제로는 한 마을에서만 순회 경로를 찾게 되면 모두 같은 경로이기 때문에 모든 마을에서 출발할 필요가 없습니다!

코드 (c++)

#include <cstdio>
#include <algorithm>

using namespace std;

const int INF = 1e9;

int N, END;
int arr[16][16];
int memo[16][1<<16];

int tsp(int city, int visited) {
    // 마지막 노드에서 출발 지점으로 이동
    if(visited == END) return arr[city][0];

    // 현재 상태를 이미 계산한 값이 있다면 사용
    if(memo[city][visited] != INF) return memo[city][visited];

    // 값이 없다면 계산
    for(int i=0; i<N; ++i) {
        if(visited & (1 << i)) continue;

        if(arr[city][i]) {
            int res = tsp(i, visited | (1 << i));
            if(res) memo[city][visited] = min(memo[city][visited], res + arr[city][i]);
        }
    }

    return memo[city][visited];
}

int main() {
    scanf("%d", &N);
    END = (1 << N) - 1;

    for(int i=0; i<N; ++i) {
        for(int j=0; j<N; ++j) {
            scanf("%d", &arr[i][j]);
        }

        for(int j=0; j<(1<<N); ++j) {
            memo[i][j] = INF;
        }
    }

    int ans = tsp(0, 1);
    printf("%d\n", ans);

    return 0;
}

실행 결과

코드 (Java)

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

// 백준 2098: 외판원순회
// TSP 알고리즘
public class 외판원순회 {

    static final int INF = (int) 1e9;
    static int[][] arr = new int[16][16];
    static int[][] memo = new int[16][1<<16];
    static int N, END;

    public static int tsp(int city, int visited) {
        if(visited == END) return arr[city][0];
        if(memo[city][visited] != INF) return memo[city][visited];

        for(int i=0; i<N; ++i) {
            if(arr[city][i] != 0 && (visited & (1 << i)) == 0) {
                int res = tsp(i, visited | (1 << i));

                if(res > 0)
                    memo[city][visited] = Math.min(memo[city][visited], res + arr[city][i]);
            }
        }

        return memo[city][visited];
    }

    public static void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        END = (1 << N) - 1;

        StringTokenizer st;
        for(int i=0; i<N; ++i) {
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<N; ++j) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }

            Arrays.fill(memo[i], INF);
        }

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

실행 결과

외판원 순회 문제(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 알고리즘을 사용해도 배열 크기 문제로 사용할 수 없는 방법이지만 모든 경로를 방문해서 구하는 방법보다는 시간이 매우 짧기 때문에 알아두면 좋을듯 함

구현

• 이 문제를 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