백준 11266번 단절점

< 백준 11266번 단절점 - 마포 코딩박>

사용한 알고리즘: DFS


 단절점을 구하는 문제였습니다.
 A번 노드가 Root가 아니고, 자식노드들이 A번을 통하지 않고는 위의 노드로 갈 수 없다면 A번 노드는 단절점 입니다. 만약 A번 노드가 Root 라면 자식트리가 2개 이상이면 단절점입니다.
 SCC, BCC 구현으로 풀 수도 있지만, DFS 만으로도 풀 수 있는 문제였습니다.

문제풀이는 다음과 같습니다.

(1) (코드 46~51)
 DFS로 모든 노드를 둘러볼 것입니다. 아직 방문하지 않은 노드가 있다면 DFS 를 시작하고, 해당 노드가 그 노드가 포함된 component의 Root 라고 생각합니다.

(2) (코드 11~36)
 DFS 를 시작할 시, 노드(이하 curr) 의 dfsn, 즉 번호를 붙여줍니다.
 DFS는 curr 에서 올라갈 수 있는 최대한 작은 번호(이하 ret) 를 return 해 줄 것입니다.
 curr 와 연결된 노드들을 둘러보며 ret 을 최신화해줍니다. 방법은 다음과 같습니다.
 1. 연결된 노드가 이미 방문됐으면, 그 점의 dfsn을 받습니다. ( 이는 curr 이 자신보다 위의 노드와 연결됐음을 의미합니다. )
 2. 아직 방문하지 않은 노드라면, 새로운 자식'트리' 가 생기는 것입니다. 해당 연결노드는 root가 아님을 표시하고 DFS를 돌려 얻은 값을 받습니다.
 3. curr이 root가 아니고, 자식트리의 return값이 dfsn[curr] 보다 크거나 같다면 curr은 단절점입니다. ( 이는 curr의 자식트리가 curr 위의 노드로 갈 수 없다는 것을 의미합니다. ) 
 4. curr이 root 이고, 자식트리가 2개 이상이라면 curr은 단절점입니다.