[BOJ]16947번: 서울 지하철 2호선

 

www.acmicpc.net/problem/16947

---

DFS/BFS 문제입니다.

 

싸이클 판별만 잘 하게 되면 DFS로 탐색하든 BFS로 탐색하든 상관없습니다.

 

<싸이클 판별하는 방법>

 

싸이클 내부에 있는 노드의 성질은 자기 자신에게 들어오는 간선이 최소 1개이상 입니다.

 

이 점을 활용하여 그래프를 입력받을 때

1. 자기 자신에게 들어오는 노드를 세주기

2. 싸이클의 후보가 아닌 노드를 제거하면서 그 노드과 연결되어 있는 노드의 간선 갯수를 하나씩 빼줍니다.

3. 이렇게 갱신을 하다가 더 이상 갱신되지 않으면 남아있는 노드들은 전부 싸이클에 속합니다.

 

이 점을 활용해서 순환선 내부에 있는 역을 파악하면 됩니다.

---

코드: github.com/cottory/algorithm/blob/master/BOJ/BOJ16947.cc