백준 2098번: 외판원 순회 [Gold 1]
//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을 적용해야 합니다.
- 문제에는 "어느 한 도시에서 출발해 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보다 더 큰 임의 값으로 지정