문제 분석
문제를 처음 보고 느낀점은, i -> j로 이동할때 그리고, 각 간선마다 비용은 존재하고, i -> j 비용과 j -> i 비용은 다를 수 있다.
위 내용까지만 보고 플로이드 와샬이 처음에는 생각났다. 혹은 다익스트라도 가능하지 않을까? 싶었다. 혹은 MST는? 라는 생각도 들었다. 문제를 풀기에 앞서 하나씩 정리를 해보자
TSP vs Dijkstra
- 다익스트라는 '단일 출발점' 에서 다른 모든 노드까지 가는 각각의 최단 경로를 구한다.
다익스트라 : A에서 B까지 가는 가장 빠른 길은?
TSP : A에서 출발해서 B, C, D를 모두 들렀다가 다시 A로 돌아오는 가장 짧은 '순회 경로'는?
차이점
-
방문 의무 : 다익스트라는 중간에 모든 노드를 방문 할 필요가 없다.
-
목적 : 다익스트라는 '경로'를 찾고, TSP는 '사이클'을 찾는다.
TSP vs Floyd-Warshall
-
플로이드 와샬 알고리즘은 '모든 노드 쌍' 간의 최단 경로를 한 번에 구해준다.
플로이드 와샬 : A->B, A->C, A->D, B->C, B ->D... 등 모든 가능한 모든 쌍의 최단 거리는 각각 얼마?
TSP : 위의 질문과 동일... '순회 경로는?'차이점
-
정보의 쓰임 : 플로이드 와샬은 "A에서 D로 가는 최단 거리는 15"라는 정보를 제공
-> TSP는 이 정보를 활용할 수 있지만, 플로이드 와샬 자체가 모두를 방문하는 '순서'를 알려주지는 않는다. -
목적 : 플로이드 와샬은 모든 노드 쌍 (NxM)의 최단거리 정보테이블을 만들고, TSP는 단 하나의 최적 순회 경로를 찾는다.
TSP vs MST
MST 알고리즘은 모든 노드를 연결하는데 필요한 '간선들의 합'이 최소가 되는 트리를 만든다.
MST: 모든 도시를 연결하는 도로망을 깔 때, 어떻게 깔아야 총 도로 건설 비용이 최소인가?
TSP : 위의 질문과 동일차이점
-
구조 : MST는 트리, 즉 '사이클이 절대 없다' TSP는 반드시 '사이클'이어야한다.
-
목적 : MST는 연결이 목적이고, TSP는 방문이 목적이다.
-
간선사용 :MST는 한 노드에서 여러 간선이 연결될 수 있다. TSP 경로에서는 모든 노드는 정확히 2개의 간선만 사용한다. (들어올때 1, 나갈때 1)
TSP는 왜 별도 알고리즘인가?
- 이유는 위 알고리즘과 '문제의 종류' 자체가 다르다.
-
조합적 폭발
- 다익스트라, 플로이드 와샬, MST는 모두 다항시간 안에 풀 수 있는 문제이다.
- 하지만, TSP는 방문할 노드가 N개일때, 방문하는 순서는 (N-1)! 가지이다. 10개만 되어도 36만개 이상.20개만 되어도 경 단위가 넘는다.
- 이처럼 최적의 경우의 수가 폭발적 증가, 앞선 알고리즘들 처럼 간단한 로직(그리디, DP)로 최적해를 찾기 어렵다.
-
문제의 본질 = '순서'
- 다른 알고리즘들은 A-> B로 가는 가장 싼 경로를묻는다.- TSP는 "A, B, C, D...를 어떤 순서로" 방문해야 가장 싼가? 를 묻는다.
즉, TSP는 '최단 경로', '최소 연결' 문제가 아니라, '최적의 방문 순서'를 찾는 조합 탐색 문제이기때문에 아예 다른 알고리즘들과 구별된다.
외판원 순회
-
우선 모든 정점에서 순회를 하고 돌아오는데 어떤 정점에서 시작해도 최소 비용은 같다. 그래서 0번이나 1번 비트로 시작한다.
외판원 순회의 복잡도 - DP + Bitmasking
시간 복잡도 : O(N^2 2^N)
공간 복잡도 : O(N 2^N) -
내용의 전체적으로 DP의 로직이다, 하지만 비트마스킹을 적용했기에 코드를 이해했다면 조금 더 쉽게 받아들여졌다.
public class Main {
static int INF = 1_000_000_000;
static int N;
static int[][] W;
static int[][] dp; // 1차원은 출발점, 2차원은 방문 체크
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
N = Integer.parseInt(br.readLine());
W = new int[N][N];
dp = new int[N][(1 << N)]; // 배열 만들고,
for (int i = 0; i < N; i++) {
Arrays.fill(dp[i], -1); // 방문 안했기에 -1로 초기화,
}
for (int i = 0; i < N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
W[i][j] = Integer.parseInt(st.nextToken());
}
}
System.out.println(dfs(0, 1));
}
static int dfs(int now, int visited) {
if (visited == (1 << N) - 1) { // 만약 모두 방문했다면 ,
if (W[now][0] == 0) { // 근데 만약 돌아갈 수 없다면,
return INF; // 무한,
}
return W[now][0]; // 아니면 최종값 반환
}
if (dp[now][visited] != -1) { // 만약 방문 했던곳이라면,
return dp[now][visited]; // 반환
}
dp[now][visited] = INF; // 일단 최대값으로 갱신해주고,
for (int i = 0; i < N; i++) { // 재귀를 타면서 Top-down 방식으로 질의,
if ((visited & (1 << i)) == 0 && W[now][i] != 0) { // 방문하지 않았고, 지나갈 수 있다면,
dp[now][visited] = Math.min(dp[now][visited], dfs(i, visited | (1 << i)) + W[now][i]);
}
}
return dp[now][visited];
}
}
