이전 외판원 순회 2에 이어서, 이번에는 골드 1 외판원 순회 문제이다.
왜 골드 1 씩이나 티어가 부여됐는지 확인을 해봤더니, 제약 조건이 달랐다.
도시의 수가 10개가 아닌 16개까지 가능해졌다.
그럼 원래 코드는 시간초과가 나겠거니 생각하고 한 번 제출해보니
당연히 시간초과가 발생했다.
도시의 수만 달라졌을 때, 어떤 다른 방식을 사용해야 시간을 줄일 수 있을까?
다시 다익스트라?
한 번 다익스트라의 사용 가능성에 대해서 생각해보자.
모든 도시를 순회해야 함이 보장되어야 하는 것이 TSP 문제의 특징이다.
그런데 다익스트라는 어떤 길을 가든 다른 정점까지의 최단거리만을 계산한다.
그 말인 즉슨 순회가 보장되지 않는다는 점이다.
그럼 다익스트라를 직접적으로 사용할 수는 없다는 말인데,
다익스트라에 얽매이지 않고 생각해보면 다익스트라도 결국 DP의 원리를 이용한다.
예를 들어, 1 - 2 - 3 - 4 - 5와 같은 순서가 있을 때, 결국 1 -> 5의 최단거리는?
1->4의 최단거리에 4->5의 최단거리를 더한 것이 된다. 그럼 1 -> 4의 최단거리는?
1->3의 최단거리에 3->4의 최단거리를 더한 것이 된다. 이렇듯 이전 단계를 이용하는,
Memoization 을 외판원 순회 문제에 적용해볼 수 없을까?
비트마스킹 + DP
너무 생각이 나지 않아 결국 다른 사람들의 풀이를 참고했다.
다른 사람들이 낸 정답들은 상당히 충격적인 풀이들이었다.
DP로 풀되, 비트마스킹을 이용해 방문사실을 확인하며 풀이한다.
우선 핵심 개념은, 한 정점에서 출발해도 모든 경우를 구할 수 있다는 것이다.
왜 그렇게 될까?
0에서 출발해서 0 -> 1 -> 3 -> 2 -> 4 -> 0과 같은 경로를 지난다고 생각해보자.
사실 해당 경로를 지나는 비용은 1 -> 3 -> 2 -> 4 -> 0 -> 1 의 경로와 같다.
또, 3 -> 2 -> 4 -> 0 -> 1 -> 3 도 동일한 비용의 경로가 된다.
즉, 이 점을 이용해서 DFS는 단 한번만 돌아도 최소 비용을 구할 수 있다!
이전 풀이였던 완전 탐색에 비해서 확실히 시간이 줄어들 것이다.
두 번째로 사용되는 개념은, 비트마스킹 이다.
방문 여부 확인을 따로 배열을 만드는 것이 아닌, 비트 연산만으로 진행하도록 한다.
예를 들어 5개의 도시가 있다면, 00000으로 시작하여 1로 방문 여부를 체크한다.
1번 도시를 방문했다면? 00001이 될 것이다.
그럼 5번 도시를 방문했다면? 10001이 될 것이다.
매 도시에 대한 방문 여부는 1 << i의 이진수로 구할 수 있다.
모든 도시를 다 방문했다면? 11111 = (1 << N) - 1로 표현할 수 있다.
두 가지를 합쳐, dp[1001][1 << 16] 크기의 배열에 비용을 갱신한다.
즉, dp[a][b] = c 의 의미는 아래와 같다.
b 도시들을 방문하고 a 도시에 왔을 때, 최소 비용은 c에요 라는 의미이다.
위의 개념들을 가진 채로 아래와 같이 문제를 풀 수 있다.
int num = 0, graph[16][16];
int dp[16][1 << 16];
int dfs(int curr, int visit) {
if (visit == (1 << num) - 1) {
// 모든 도시를 다 방문했다면?
if (graph[curr][0] == 0)
return INF;
// 출발지를 의미하는데, 출발지가 0이라면 갈 수 없는 곳이다.
// INF를 반환
return graph[curr][0];
// 출발지가 갈 수 있는 위치라면, 출발 지점까지의 비용 반환
}
if (dp[curr][visit] != -1)
return dp[curr][visit];
// -1로 처음에 초기화를 했었다.
// -1이 아니라는 것은, 이미 탐색한 상태라는 것!
// 해당 상태에서의 최소 비용을 반환한다.
dp[curr][visit] = INF;
// -1이라는 것은, 아직 탐색하지 않은 지점이라는 것
// 비용 갱신을 위해 INF로 갱신한다.
for (int i = 0; i < num; i++) {
if (graph[curr][i] != 0 && ((visit & (1 << i)) != (1 << i)))
// 탐색을 진행하는 경우는, 해당 도시로 가는 길이 있어야 한다.
// 또한 방문하지 않은 도시여야 하기 때문에 우측과 같은 비트 연산을 진행한다.
// visit & (1 << i)를 했을 때, 방문하지 않은 도시라면 0으로 바뀌게 된다.
// 따라서 1 << i와 형태가 반드시 달라질 것!
dp[curr][visit] = min(dp[curr][visit], graph[curr][i] + dfs(i, visit | 1 << i));
// 배열에는 방문한 도시 상태에 대하여, 현재 도시까지의 거리를 갱신한다.
// 재귀를 통해 도시를 모두 방문할 수 있도록 한다.
// i와 visit | 1 << i를 넘긴다는 말은, 다음 도시와 그 도시를 방문한 상태를 넘기는 것이다.
}
return dp[curr][visit];
// 모든 도시를 탐색한 뒤, 현재 상태에서의 비용을 반환한다.
}이런 문제처럼 아예 새로운 개념을 만나게 되면 굉장히 당황스럽다.
사실 문제를 완전히 이해하고 푼 상태도 아니다. 풀이가 너무 어렵다.
평범하게 생각하는 사람의 입장에서, 매우 생각해내기 힘든 풀이라고 생각한다.
이럴 땐 나는 이 개념 관련 문제만 주루룩 풀어서 머리에 익히도록 한다.
새 개념들을 알게될 때 마다 문제를 풀 수 있는 길이 하나씩 느는 거라고 생각한다.
이 문제는 다음에 꼭 두 번 세 번 더 보도록 하자.