백준 2098(1) (외판원 순회)

백준 2098 외판원 순회 (1)

문제 링크

문제 링크 : https://www.acmicpc.net/problem/2098

들어가기에 앞서

동적 계획법(dynamic programming) 두 번째 국룰 문제 외판원 순회 (tsp, traveling salesman problem) 문제입니다. 출처 : https://xkcd.com/399/

컴공생이라면 한 번쯤은 들어본 외판원 순회 문제입니다. 외판원 순회 문제(traveling salesman problem)에 대해 간략하게 설명을 해보겠습니다. n개의 도시가 주어졌을 때, 방문 판매원은 모든 도시를 순회한 후, 시작점으로 돌아와야 합니다. 이 때, 최소 비용을 드는 경로를 구하는 문제입니다. 즉, 가중치 그래프가 주어졌을 때, 최소 비용의 해밀턴 순환(hamilton cycle)을 찾는 문제입니다.

해밀턴 순환

해밀턴 순환을 알기 위해서 해밀턴 경로를 이해해야 합니다. 그래프가 주어졌을 때, 모든 노드를 단 한 번 지나는 경로입니다. 해밀턴 순환은 해밀턴 경로 + (시작==끝)인 경로라고 이해할 수 있습니다.

문제 접근

처음 봤을 때, 마땅한 아이디어가 떠오르지 않습니다. 따라서 완전탐색으로 시뮬레이션을 해보도록 하겠습니다. 그래프에서 각 노드들은 다 연결이 되어 있다고 가정하겠습니다. 즉 간선의 수가 n(n-1)개 있다는 의미입니다.
(왜 n(n-1)/2가 아닌가요? 라고 묻는다면, 가중치 그래프기 때문입니다.
a,b 노드에 a->b (cost1), b->a (cost2) 의 간선이 2개 달려있다고 생각할 수 있기 때문입니다.)

맨 처음 가능한 경우의 수는 n입니다. 아무 도시나 고르면 되기 때문입니다. 두 번째로, 가능한 경우의 수는 n-1입니다. 다음의 경우의 수는 n-2입니다. 즉 O(n!)의 시간 복잡도를 갖는다고 할 수 있습니다. 팩토리얼은 매우 강력합니다. n=12만 되어도, 대략 479001600(12!)의 연산을 해야 합니다. 실전에서 써먹을 수 없는 알고리즘으로 보입니다.

n!의 의미

다른 생각에 앞서서, n!에 대해서 해석을 해봅시다. 이 의미는, 처음에 가능한 n개의 도시에 대해서 다 탐색을 해보자는 의미입니다. 하지만 조금 생각을 해 본다면 전혀 그럴 필요가 없습니다.

왜냐하면, 결국 우리는 최소 비용을 갖는 경로만 구하면 되기 때문입니다. 경로라는 것은 고정이 되어 있고, 어차피 각 정점을 무조건 지날 것임은 자명한 사실입니다.

처음에 n개의 정점에 대해 모든 경로를 탐색하지 않고, 아무거나 하나의 정점을 잡아도 된다는 의미입니다. 어차피, 최단 경로만 구하면 되기 때문입니다.

그렇다면 O(n!)이 아닌, O((n-1)!)으로 해결이 가능해집니다. 그럼에도, 실제 세계에서 쓰기는 매우 힘들어보입니다. !(팩토리얼)의 증가율은 엄청 가파르기 때문입니다.

이제, 완전 탐색으로 풀기에는 매우 힘들어 보임을 알았습니다. 다른 아이디어를 생각해봅시다.

탐욕법으로 풀어도 optimal한 solution을 내기 힘들어 보입니다. 돌아가는 길이 더 비용이 작을 수 있기 때문입니다. 따라서, 동적 계획법으로 접근을 해보자는 것입니다.

동적 계획법에 앞서, 전체 문제를 부분으로 쪼갤 수 있고, 각 최적의 부분을 합치면 전체의 최적이 된다는 명제는 자명해 보입니다. 해밀턴 순환 경로를 2개로 나누었을 때, 하나라도 최적의 경로가 존재하지 않는다면, 전체의 최적은 만족할 수 없기 때문입니다.

이제 상태(state)를 정의해 봅시다. 현재 상태는 내가 이때까지 방문했던 도시, 현재까지의 비용으로 정의할 수 있습니다. 이들을 잘 memoization한다면, O(n!)의 시간 복잡도를 갖는 완전탐색 알고리즘보다 훨씬 좋은 성능을 낼 것 같습니다.

마무리하며

내용이 너무 길어질 것 같습니다. 한 번 끊고, 다음 포스팅에서 뵙겠습니다.