추석맞이 POI풀이: 동굴 탐험

한참 고민하다가 쿠사가님으로부터 힌트를 듣고 풀었다(원본 풀이는 큐브러버님 것이라고 함). 오늘 쉬운 것만 푼 것 같아서 이 문제를 잡았는데 정말 좋은 풀이여서 풀길 잘했다는 생각이 들었다.

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

문제 요약

n개의 정점과 m개의 간선으로 이루어진 그래프가 있다. 각 간선은 a b c d로 표현되는데, 이는 a->b로 갈때는 비용이 c이고 b->a로 갈때는 비용이 a라는 뜻이다. 이 그래프에서, 1번 정점에서 시작해서 다시 1번 정점으로 돌아오는 최단 경로를 구해야 한다.

이 때,

1. 모든 정점과 간선은 딱 한 번만 지나갈 수 있다(1번 정점 제외)

2. 1번 정점 외의 정점을 반드시 하나는 거쳐야 한다.

문제 풀이

1번 정점에서 임의의 정점 k를 거쳐 다시 1번 정점으로 돌아오는 문제로 생각해보자. 이 경우, 1->k로 가는 정점의 비용을 빼놓고 보면 k->1로 가는 최단거리를 구하는 문제로 생각할 수 있고, 이는 다익스트라를 이용해 구할 수 있다. 왜냐하면, 다익스트라를 통해 계산했을 때 k->1로 가는 최단거리에 같은 정점과 간선이 두 번이상 포함될 이유가 없기 때문이다(한 번만 포함하는 경로가 더 짧은 경로이므로). 따라서, 양 방향 비용을 별도로 두 개의 엣지로 생각하고 다익스트라를 돌려도 답이 된다.

이런 방식으로 구할 경우, 1번 정점과 연결된 모든 정점 k에 대해서, 이 정점 k로부터 시작해서 최단경로를 구하면 N번 다익스트라를 수행하면 되므로, O(N * M * logN)이 된다. 하지만 N 제한이 5000, M 제한이 10000에 logN이 붙어서 시간 제한 1초 안엔 답이 나오지 않는다.

이제 이걸 개선해보자. 똑같이 다익스트라로 수행하되, 한 번에 여러 개의 쌍에 대해서 답을 구해 볼 것이다.

아까 구한 방법을 좀 더 명확하게 정리해보자. 1 -> i -> ... -> j -> 1로 가는 경로의 경우, 1에서 i로 가는 비용을 C(i), i에서 j로 가는 최단 거리를 D(i,j), j에서 1로 가는 비용을 C(j)라고 하면 C(i) + D(i,j) + C(j)가 최단 거리가 된다. 즉, 모든 i, j쌍에 대해서 C(i) + D(i,j) + C(j)의 최솟값을 구하는 문제로 생각할 수 있다.

이 때, 만약 모든 i와 j가 서로 다른 집합에 속한다면(시작점과 끝점 간에 겹치는 점이 없다면), 이들 쌍 간의 D(i,j)는 한 번의 다익스트라로 바로 구할 수 있다. 좀 더 명확히 설명해보자.

시작점 집합을 S, 도착점 집합을 T라고 하고, S와 T의 교집합은 공집합이다. 여기서 S에 속한 정점 i에 대해 시작 거리를 C(i)로 초기화한 후, 이 정점들로부터 다익스트라를 수행한다. 다익스트라를 통해 얻은 j번 정점까지의 최단 거리를 D(j)라고 하면, D(j) + C(j) 가 임의의 S 집합의 한 정점에서 출발해서 j 정점으로 가는 최소 비용이 된다. 왜냐하면, C(i)값은 처음에 초기화하면서 고려해줬고, 이 후 정점을 지나가면서 j에 도달하는 최단거리를 구했기 때문에 j 정점 입장에서는 D(j) 값이 임의의 i정점에서 출발해서 j에 도착하는 최단거리 값이 되기 때문이다.

이 방법을 이용해서 다익스트라 수행 횟수를 획기적으로 줄일 수 있다.

주어진 정점을 두 개의 집합으로 분리해보자. 1번 집합을 S, 2번 집합을 T로 놓으면 다익스트라 한 번으로 S 집합의 임의의 정점에서 시작해서 T 집합의 임의의 정점에 도달하는 모든 최단거리를 구할 수 있다. 이 값을 구하고 나면, 이제 S 집합 내부의 정점 간의 최단 거리와 T 집합 내부의 정점 간의 최단 거리를 구해야 한다.

여기서 다시 S 집합을 S1, S2로 이등분하고, T 집합을 T1, T2로 이등분해보자. 추가로 구해야 하는 건 S1 -> S2 의 최단거리과 T1 -> T2의 최단 거리다. 이는 다시 시작 정점 집합을 (S1, T1) 의 합집합으로 두고 도착 정점 집합을 (S2, T2)의 합집합으로 두고 최단거리를 구해보자. 이 최단거리는 S1->S2, S1->T2, T1->S2, T1->T2의 최단거리를 계산하게 되고 이 최단거리에 S1 -> S2와 T1 -> T2가 포함되어 있으므로 이 최단거리를 구하는 것으로 충분하다. 따라서 이러한 방법을 반복해서 구간을 계속 절반씩 나눠나가면서 다익스트라를 수행하면 O(logN)번의 다익스트라로 답을 구할 수 있다.

여기서 집합을 계속해서 이등분하는게 좀 까다롭게 느껴질 수 있는데, 정점 번호를 비트 단위로 분할해서 다익스트라를 수행하면 계산하기가 굉장히 편하다. 즉, i번째 비트가 0인 정점과 i번째 비트가 1인 정점은 항상 서로 다른 집합에 속하기 때문에, 이를 기준으로 정점 집합을 분할해서 답을 구하면 구현이 굉장히 편리하다.