BOJ 13911 집 구하기

이 문제는 고민 좀 했는데... 알고보니 내가 예전에 풀었던 유형이었다.
SCPC 예선에도 나왔었고, JM book에 나와있는 유명한(?) 문제 유형이다.

문제를 잘 읽어보면 결국은 맥날과 스벅 사이의 최단 거리를 구하는 문제로 볼 수 있는데, 맥날이랑 스벅의 수도 여러 개이고 정점의 수도 10000개라 다익스트라를 여러번 돌려서는 시간 초과가 날 것이다.
하지만 그래프를 조금만 변형 해보면 맥날과 스벅사이의 최단 거리를 다익스트라 한 번으로 구할 방법이 있다. 바로 새로운 출발점을 하나 만들고 거기에 가중치 0의 간선으로 모든 맥날(또는 모든 스벅)과 연결하는 것이다. 그리고 그 출발점에서 출발하여 각 정점까지의 최단 거리를 구하는 다익스트라 알고리즘을 이용하면 각 맥도날드에서 각 스벅까지의 거리 중 최단 거리를 찾을 수 있다. 참 처음에 이 방법을 JM book에서 봤을 때, 정말 기가막히다고 생각했는데 지금 다시 봐도 멋진 방법이다.

그런데 이 문제는 조금 더 생각해야 할 것이 있다.
바로 맥날과 스벅사이의 경로에 맥날과 스벅이 아닌 일반 집 하나가 꼭 있어야 한다. 예를 들어 맥날 - 스벅 이렇게 최단 거리일 경우 답이 될 수 없다.
음 맥날과 스벅이 정점 번호로 여러 개 주어지는데, 이걸 다 일일이 비교해서 집인지 아닌지 판별해야 하나? 그럼 너무 오래 걸릴텐데...

다익스트라 알고리즘을 생각해보면 일단 시작하자마자 각 맥날까지의 최단 거리는 0이다. 그렇기 때문에 다른 맥날에서 맥날을 거쳐갈 일이 없다.(그 맥날까지의 거리가 더 짧은 거리로 갱신돼야 하는데 이미 0이므로 갱신될리가 없다.) 즉, 맥날에서 어떤 정점까지의 경로는 출발점 바로 다음의 맥날 하나 뿐이다. 그 외의 맥날은 없다.

그렇다면 스벅은 어떨까? 맥날부터 어떤 스벅까지의 경로에는 분명 다른 스벅이 있을 수 있다. 하지만 다른 스벅을 거쳐 도착한 스벅까지의 경로는 절대 맥날-스벅 간의 최단 거리가 될 수 없다. 왜냐하면 이미 그 전에 거친 스벅 바로 거기까지의 거리가 더 짧을 것이기 때문이다.

즉, 맥날부터 스벅까지의 최단 거리를 구하되, 맥날부터 스벅까지 몇 개의 길을 거쳐갔는지 기록해서 .... 가 아니라.. 안된다. 몇 개의 길을 거쳤는지 기록해서 원래 2개 이상 거친 것 중에서 최단 거리를 찾으려 했지만 그럴 경우 중간에 스벅이 끼어있고 일반 집은 없을 수도 있다. 이런 경우를 커버할 수 없다.

꽝이다! 잘못 생각했다.
그리고 다시 생각해보니 이 문제는 무작정 맥날과 스벅사이의 최단 거리를 구하는 문제는 아닌 것 같다. 왜냐하면 어떤 집이 꼭 맥날과 스벅 사이에 있어야 할까? 아니다
맥날 - 집 - 스벅 이 아닌 맥날 - 스벅 - 집 일 수도 있다!!! 왜냐하면 문제에서 구하라는 것은 집의 맥도날드까지의 최단거리와 스타벅스까지의 최단거리 합이므로...

그렇다면 어떻게 해야할까?
생각해봤다.
다익스트라를 두 번 돌린다. 처음에는 새로운 출발점을 맥날들에 연결하고 시작해서 일단 일반 집까지의 최단 거리를 다 구하고, 또하나의 새로운 출발점을 일반 집들에 연결하되 간선의 가중치는 앞서 구한 맥날에서 각 집까지의 최단 거리로 놓는다. 그리고 dist배열을 다익스트라 처음 시작할 때 처럼 다 초기화한 후 그 출발점에서 시작해서 최단 거리를 구해서 스벅까지의 최단 거리를 보면 결국 맥날 - 집 - 스벅까지의 최단거리를 알 수 있게 될 것이다.

위와 같이 하면 첫 다익스트라에서 각 집에서 맥날까지의 최단 거리를 구했을 것이고 두번째 다익스트라에서 각 집에서 스벅까지... 아!!!

이것도 맞지만 그냥 각 집에서 처음부터 시작하면 되는 거 아닌가? 그럼 다익스트라를 한 번만 돌리면 될 것이다. 각 집에 새로운 출발점을 간선 가중치 0으로 연결하고 각 집에서 출발한다. (아니면 각 집들을 거리 0으로 바로 큐에 다 넣고 시작해도 똑같다.)
그렇게 다익스트라를 돌리면 집에서 맥날까지의 최단거리, 집에서 스벅까지의 최단거리가 구해져 있을텐데... 음 아 이럴경우는 어떤 집에서 출발했는지 알 필요가 있으므로 같은 집에서 출발한 최단거리끼리 합치고 그 중 최소값을 구하면 될 것이다. 다익스트라를 한 번만 돌리는 대신 출발점이 어딘지를 기록해야 하고 비교해서 같은 것 끼리 더하고 그 중 최소값을 찾는 과정이 필요하다.

두 방법 모두 다 해봐야겠다. 아 그리고 맥세권, 스세권 모두 되는지 확인하는 것도 필요하다!

집에서 출발하는 것으로 구현중인데, 같은 집에서 출발한 것을 찾는게 O(N제곱)짜리 밖에 떠오르지가 않는다... 처음에 생각한 방법처럼 맥날들 부터 시작해서 다익스트라를 2번 돌려야겠다.
아 근데... 또 하나의 문제에 직면했다. 바로 맥세권 스세권을 따져주는 것인데, 각각 멕세권인지 스세권인지 따져야 하므로 좀 까다롭다...
일단 처음에 맥날에서 집까지의 거리는 맥세권 제한 x이하인 경우만 보는 걸로 처리하면 되는데, 각 집에서 (맥날에서의 최단 거리를 가지고) 출발해서 스벅까지의 최단거리를 구하는 과정에서가 문제다. 이 것을 해결하기 위해 아까 했던 것 처럼 출발점이 어딘지를 기록해서 최단거리를 다 구한 후 답을 구할 때, 스벅까지 최단거리-(출발점까지의 거리)의 값이 스세권 제한 y이하인지 판별해야 할 것 같다.

일단 그렇게 해서 AC를 받았다....
이 문제... 쉬운 줄 알았는데 그렇지 않았다.

그리고 생각해보니 집에서 출발해서 각 최단 거리를 구하고 출발지가 같은 것을 합하는 방식은 반례가 있다. 안된다...
예를 들어 맥날까지의 최단 거리는 집1에서 부터의 거리이고, 스벅까지의 최단 거리는 집2에서부터의 거리이고 답은 맥날 - 집1 - 집2 - 스벅 인 경우를 처리할 수 없다...
 
하지만 내가 맥날에서 집까지의 최단 거리를 구하고 그 값들을 가지고 각 집들에서 스벅까지의 최단 거리를 구하는 것은 잘 생각해보면, 집을 경유하는 (맥날에서 스벅까지의) 최단 경로를 구하는 것과 같기 때문에 가능한 것 같다.

좀 헷갈리기도 하고, 정말 좋은 문제였다.

그리고.. 다른 분들의 풀이를 보고 있는데.... 헉... 더 좋은 방법이 있었다.
맥날에서 각 집까지의 (맥세권인)최단 거리를 구하고, 스벅에서 각 집까지의 (스세권인)최단 거리를 구한 후 각 집을 기준으로 두 최단 거리를 합쳐서 그 중 최소값을 구하면 된다...

와... 이거 어디서 본 것 같은데.. 익숙한 방법인데 난 전혀 생각도 못하고 괜히 어렵게 생각하고 있었다. 이렇게 하면 또 좋은 것이 맥세권인지 스세권인지 판단하기 편하다 그냥 다익스트라 함수 내부에서 바로 각 집까지의 거리가 맥세권이나 스세권인 경우만 처리하면 된다.
그리고 훨씬 이해하기도 좋은 방법같다. 문제를 많이 풀어보고 공부도 많이 해야한다...