SWERC 2019 K. "Bird Watching"

algorithm-ps ― [ swerc-2019 , BOJ ]

SWERC 2019 K번 문제이다. BOJ 18303번이기도 하다.

rkm0959한테 문제 요약만 들어서 본문을 잘 모른다(…)

Unweighted Directed graph에서 어떤 고정된 정점 \(T\)에 대해 \(u \to T\) 간선이 있고, 이 간선을 사용하지 않으면 \(u\)에서 \(T\)로 이동할 수 없는 정점 \(u\)를 모두 구하는 문제이다. 정점 개수와 간선 개수는 $10^{5}$개 이하.

Solution

뇌정지가 오기 쉬운 문제같다. 풀이도 말로 하기가 어려운듯…

일단 모든 간선의 방향을 뒤집어서 생각하면 시작점이 \(T\)로 고정된다. 기본적인 세팅.

한 가지 관찰은 \(T \to u\) 간선이 \(T\)에서 \(u\)로 가는 가장 짧은 경로라는 것이고, 이 간선을 사용하지 않는 경로는 모두 길이가 그보다 strict하게 길다는 것이다.

이제 \(T\)에서 나가는 간선을 모두 제거하자. \(T\)에 인접한 모든 \(u\)들을 시작점으로 하는 multi-source dijkstra 알고리즘을 돌리되, 서로 다른 시작점에서 온 최단 경로 2개를 유지한다. 그냥 BFS로 되는 것 같기도 한데 확신이 없어서 heap 다익스트라를 썼다.

이 때 시작점으로 쓴 \(u\)들 중 2번째 최단경로가 없는 점들이 우리가 원하는 조건을 만족한다.

Written on March 5, 2020