BOJ 18303

https://www.acmicpc.net/problem/18303

 

코드

http://boj.kr/fe36e3b0eef6488098fb5a81110b80f3

 

Southwestern European Regional Contest SWERC 2019 K

 

난이도 : P2

 

Elapse time : 50min

 

문제 지문이 복잡하여 이해하는데 시간이 꽤 걸렸다. 문제 이해를 하고 나니 문제의 요구사항은 꽤 간단했다. 유향그래프 $P$에서 한 정점 $T$가 주어졌을 때 $P$에 있는 정점 중 $T$로 향하는 간선이 있는 정점들을 생각하자. 그 정점들 중 $T$와 직접 연결된 간선을 거치지 않으면 $T$로 도달할 수 없는 정점들을 모두 구하는 문제였다. 우선 $T$로 향하는 간선이 존재하는 모든 정점들에 대해 그래프 탐색을 진행하면 시간초과가 발생할 것이기 때문에 그래프의 경로들을 모두 뒤집고 $T$에서 $dfs$를 돌려 문제를 해결할 생각을 했다. 첫 풀이는 $dfs$를 하되 $T$에서 바로 가는 간선을 사용할 경우 $visited$배열에 표시를 하지 않는 것이었다. 그러나 $T$에서 직접 연결된 간선이 있고 다른 방법으로는 갈 수 없는 정점 $S$에 대해 $S$를 포함하는 사이클이 있으면 다른 방법으로 갈 수 있다고 판단하게 되는 문제가 있어 WA를 받았다. 이를 어떻게 수정할까 고민하던 중 한 정점을 $T$에서 시작하는 서로 다른 두 간선으로 시작하여 도달할 수 있는지를 판단하기로 했다. $dfs$를 하면서 각 정점에 그 정점에 도달하기 위해 처음 선택한 간선을 최대 2개까지 저장하도록 하였다. $dfs$가 끝난 후 $T$와 연결된 모든 정점에 대해 저장된 간선이 1개라면 다른 간선으로 출발했을 때 도달할 수 없었다는 뜻이므로 답에 추가하여 해결하였다.