문제
https://www.acmicpc.net/problem/31566 - 힘세고 강한아침 (G3)
문제 요약
조금 복잡하게 표현되어있지만 이것은 그냥 일반적인 그래프에 대한 설명입니다.
1 ~ N까지의 번호가 매겨진 노드가 있습니다.
그리고 각 노드 사이에는 특정한 가중치를 가지는 간선이 있습니다.
이때 임의의 A번 노드에서 B번 노드로 갈때 C번 노드를 거치지 않고 가는 경로가 있는지, 있다면 그 최소 비용은 얼마인지 찾아야합니다.
풀이
거치지 않는 노드
임의의 노드를 지나면 안된다는건 간단합니다. 최소 비용 구하는 과정에서 해당 노드를 연산에서 제외시키면 됩니다. 그래프 탐색의 어떤 방법을 쓰던 (BFS, DFS, 벨만 포드, 다익스트라, 플로이드 워셜) 다 쉽게 적용할 수 있습니다.
쿼리가 많아
임의의 노드 s에서 e로 가는 최소비용을 구하는 것은 매우 간단하고, 위에서 이야기했든 임의의 k번 노드를 지나지 않는 비용을 구하는 것도 간단합니다.
다만, 보면 노드의 개수가 최대 100개이고 쿼리가 최대 20만번 주어집니다.
쿼리가 너무 많기 때문에 그때 그때 모든 계산을 할 수는 없고 입력으로 들어올 수 있는 모든 경우에 대해 미리 계산을 해둔 후 입력에 따라 계산해둔 값을 출력해야합니다.
시간 복잡도
그럼 모든 s, e, k에 대해 가능한 경우를 구하면 되겠네요!
가능한 알고리즘은 3가지 입니다.
- 벨만 포드
임의의 노드 a에서 다른 모든 노드로 가는 비용을 구합니다.
이 경우에선 거치면 안되는 노드가 있고, 모든 시작 노드를 고려해야하기에 벨만포드를N^2번 돌려야합니다.
-
다익스트라
임의의 노드 a에서 다른 모든 노드로 가는 비용을 구합니다.
이 경우에선 거치면 안되는 노드가 있고, 모든 시작 노드를 고려해야하기에 다익스트라를N^2번 돌려야합니다. -
플로이드 워셜
모든 노드에서 다른 모든 노드로 가는 비용을 구합니다
이 경우에선 거치면 안되는 노드가 있기에 플로이드 워셜을N번 돌려야합니다.
이제 각 경우의 시간복잡도를 확인해봅시다.
각 그래프에 있는 최대 간선 개수를 M이라 할때 다음과 같이 동작합니다.
-
벨만 포드
O(N*M)
벨만 포드를N^2번 돌리면O(N^3*M)이 되고M이 최대N*N이기에O(N^5)가 됩니다.
이는N = 100에서 연산량이 100억이 나오게 되고 확실하게 시간 초과가 발생합니다. -
다익스트라
O(N^2)
다익스트라를N^2번 돌리면O(N^4)이 됩니다.
원래는
O(노드 개수 * 한 노드에 최대 간선 수)이지만 여기선 한 노드 최대 간선 수가 N이기에O(N^2)으로 표현합니다.
이는 N = 100 에서 연산량이 1억이 나오게 됩니다.
- 플로이드 워셜
O(N^3)
플로이드 워셜을N번 돌리면O(N^4)이 됩니다.
이는N = 100에서 연산량이 1억이 나오게 됩니다.
1억회 연산 == 1초?
많은 사람들의 인식에 남아있는 것이 있습니다.
1억회 연산은 1초동안 돌아간다.
이것대로라면 이 문제의 시간제한은 1초이기에 최대 1억번 연산만 가능해야 맞습니다.
그런데 아니 이럴수가! 가장 작은 연산량이 1억이네요? 사실 그냥 단순히 계산해서 1억이지 작은 계산들을 합치면 1억을 넘을 것 입니다.
정답이 아닌 걸까요?
아닙니다. 1억회 연산은 1초 내에 충분히 돌아갑니다.
플로이드 워셜 방식을 쓴 코드인데 1초 제한에 충분한 0.1초대가 나옵니다.
1억회 연산 = 1초는 매우 널널하게, 매우 큰 상수가 붙는 경우까지 고려한 큰 값인데 사람들은 이걸 절대치라 생각하고 두려워하곤 합니다.
플로이드 워셜을 선택한 사람들은 크게 문제 없지만, 다익스트라를 선택한 사람들 중에서 일부는 이 방식으로 계산을 해보고 고민에 빠질 겁니다.
n log n 다익스트라는 항상 옮다?
사실 다익스트라는 O(N^2) 방식도 있지만 O(N log N)로 알려진 방법도 있습니다. 중간 과정에 힙을 쓰는 방식인데요.
O(N^2) 다익스트라를 생각한 후 시간 복잡도를 계산해본 사람들은 아 안되구나! 한 뒤 더 작은 시간 복잡도를 가지는 O(N log N) 다익스트라를 떠올리게 됩니다.
그럼 음.. O(N^3 log N) 이니까 대략 600만 정도겠네요. 옳거니! 이거구나 제출합니다.
하지만 시간초과가 발생합니다.
사실 저희에게 애매하게 O(N log N) 다익스트라로 알려진 방식은 사실 O(M log N)입니다. M이 위에서 이야기했듯 그래프 전체의 간선 개수이기에 이 문제 같은 경우 O(N^2 log N)이 나오게 됩니다. 이는 N = 100 에서 7억의 시간복잡도를 가집니다.
모든 노드끼리 간선이 이어진 완전 그래프에서는 힙 다익스트라가 더 느립니다.
풀어보자
두 가지 알고리즘이 남았습니다. 각각 다음과 같이 풀면 됩니다.
-
N^2다익스트라
dist[N][N][N] 배열을 선언합니다.
dist[k][s]를 k번을 거치지않고 s번에서 시작이라 두면 dist[k][s][1~N]에 다익스트라를 진행하면 됩니다.
이것을 모든 k,s에 대해 반복합니다. -
플로이드 워셜
dist[N][N][N] 배열을 선언합니다.
dist[k]를 k번을 거치지 않는다 두면, dist[k][1~N][1~N]에서 플로이드 워셜을 진행하면 됩니다.
이것을 모든 k에 대해 반복합니다.
이후 들어오는 쿼리에 따라 답하면 됩니다.
출제 의도
이 문제는 플로이드 워셜을 쓰면 쉽게 풀립니다. 실제 정해도, 태그도 다 플로이드 워셜입니다.
이 문제는 1억 연산 = 1초를 굳게 믿고있는 사람을 고민하게 만들고 힙 다익스트라가 항상 N^2 다익스트라보다 빠르다고 생각하는 사람의 시간 초과를 노린 문제였습니다.
실제로 매우 많은 시간 초과가 있는 걸 보면 나름 역할을 다하고 있는 듯 합니다.
여담
제목은 내용인 '번역' 에 맞게 어색한 번역으로 유명한 왈도체에서 따왔습니다.
