Codeground - 대피소 [SCPC 2016 - 1차 예선]

간선에 가중치가 있는 연결된 무방향 그래프가 주어지는데, 이 그래프의 정점들 중 일부는 대피소로 지정이 되어있다. 그리고 각각의 정점에서 가장 가까운 대피소를 찾고, 그 대피소까지의 거리를 구하는 문제인데,  정점의 개수는 최대 10만 개, 간선의 개수는 최대 50만 개, 그리고 대피소의 개수는 최대 10만 개(항상 대피소의 개수<=정점의 개수)이다. 시간 제한은 1초이다.

그냥 딱 떠오르는 것을 적자면, 각각의 정점에서 다익스트라 알고리즘을 이용해 대피소까지의 최단거리를 구한 후 그 중 최소를 구하면 될 것 같다. 하지만 다익스트라의 시간 복잡도는 O(ElogE) (E : 간선의 개수)... 이므로 V*ElogE...가 되어 시간 내에 불가능하다.

그렇다면 어떻게 해야할까... 아이디어가 필요하다.
일단, 무방향 그래프이기 때문에 각 정점에서 각 대피소까지의 최단 거리는 각 대피소에서 각 정점까지의 최단 거리와 같다. 음... 하지만 대피소 역시 최대 10만 개 이다. 그럼 dijkstra를 최대 10만 번 돌려야 하나...결국 각 정점에서 dijkstra를 실행하는 것이나 다를 바가 없다.
하지만 dijkstra를 한 번만 사용할 방법이 있다. 새로운 정점 src를 하나 더 만들자. 그리고 그 정점과 대피소들을 연결하는 간선을 만들고 그 간선의 가중치는 0으로 둔다.
그러면 새로운 정점src에서 dijkstra를 이용하면, src에서 각 정점까지의 최단 거리를 구할 수 있는데, src에서 각 대피소까지의 거리는 0이므로 결국 각 정점에서 가장 가까운 대피소까지의 거리를 구한 것이 된다.
<프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략 - 구종만 / (종만북, JM Book) > 이 책에 이와 비슷한 문제와 풀이가 나와있다.

자 그런데, 이 문제에서는 가장 가까운 대피소가 여러개일 경우 번호가 작은 대피소를 선택해야하는 문제가 또 있다. 이 것은 어떻게 해결할까? 여러 방법이 있겠지만, 나는 대피소의 번호를 담는 shelter라는 배열을 만들어서, dijkstra를 이용해 최단 거리를 구하는 과정에서 here->there로 가는 더 작은 경로를 찾을 때마다 shelter[there]를 처음부터 here까지 전해져 온 대피소의 위치(shelter[here])로 갱신해준다. 그리고, here->there로 가는 같은 크기의 또 다른 경로가 발견될 경우, 이미 존재하는 shelter[there]와 같은 크기의 또 다른 경로로 전해져 오는 대피소의 번호shelter[here]와 비교해서 더 작은 번호를 shelter[there]에 넣는다.
그리고 여기서 주의해야할 점이 here->there로 가는 같은 크기의 또 다른 경로가 발견될 때는 shelter만 업데이트 해주고, 그 경로를 pq에 넣지 않아도 된다. 왜냐하면 이미 그 값(dist[there])은 dist[here]보다 크서 pq안에 있기 때문이다.

자세한 구현은 조금 더 신경써야할 것이 있지만 일단은 크게 보면 이런 식으로 구현을 해서
만점을 받았다.