고정 헤더 영역
상세 컨텐츠
본문
1. 문제 : https://www.acmicpc.net/problem/11266
11266번: 단절점
첫째 줄에 두 정수 V(1≤V≤10,000), E(1≤E≤100,000)가 주어진다. 이는 그래프가 V개의 정점과 E개의 간선으로 이루어져 있다는 의미이다. 다음 E개의 줄에는 간선에 대한 정보를 나타내는 두 정수 A, B
www.acmicpc.net
2. 풀이 : DFS
3. 시간복잡도 : O(V+E)
4. 설명
단절점이란 그 정점을 제거 했을 때, 그래프가 두 개 이상으로 나누어지는 정점을 의미한다.
그림[1]에서 단절점은 1, 3, 4, 6 정점이 해당한다.
시작점(루트)을 1번 정점으로하여 DFS로 스패닝트리를 만들고, 각 정점의 진입 순서를 표기하면 그림[2]와 같다.
그림[2]에서 단절점들의 공통된 특징을 살펴보면, 특정 정점에서 그 정점보다 진입 순서가 늦은 정점이 그 정점보다 진입 순서가 빠른 정점들과 우회 경로가 없는 경우가 존재하면 그 정점은 단절점이라는걸 알 수 있다.
ex) 3번 정점보다 진입 순서가 늦은 8, 11, 12번 정점은 우회 경로가 존재하지 않으므로 3번 정점은 단절점이다.
ex) 10번 정점보다 진입 순서가 늦은 4, 5, 7번 정점은 우회 경로(1번 정점을 통과하는 경로)가 존재하므로 10번 정점은 단절점이 아니다.
ex) 4번 정점보다 진입 순서가 늦은 5번 정점은 우회 경로가 존재하지만, 7번 정점은 우회 경로가 존재하지 않으므로 4번 정점은 단절점이다.
우회 경로의 존재 유무는 DFS 탐색 시에 자식이 return 해주는 진입 순서의 최소값과 자신의 진입 순서를 비교해서 알 수 있다.
자식이 return 해주는 진입 순서의 최소값이 자신의 진입 순서보다 크거나 같다면, 우회 경로가 없다는 의미이므로 그 정점은 단절점이 된다.
그림[3]에서 모든 단절점들은 자식에게서 return 받은 진입 순서의 최소값이 자신의 진입 순서보다 크거나 같다는 것을 알 수 있다.
여기서, 시작점(루트)의 경우 한 가지 예외 상황이 발생한다. 시작점보다 진입 순서가 빠른 정점은 존재하지 않기 때문에
시작점은 무조건 단절점이 된다. 그림[4]와 같은 경우에 시작점(1번 정점)은 단절점이 되어서는 안된다.
그림[3]과 그림[4]를 비교하여 생각해보면, 시작점(1번 정점)은 자식이 2개 이상일 때만 단절점이 된다는 것을 알 수 있다.
단, 그림[5]와 같이 사이클 구조가 되는 경우에는 자식이 2개 이상이어도 단절점이 될 수 없기 때문에 DFS로 진입할 수 있는 자식의 숫자만 세어주어야 한다.
따라서, 단절점의 판단은 다음과 같다.
1) 시작점(루트)인 경우는 루트에서 DFS로 진입할 수 있는 자식의 갯수로 단절점을 판단
2) 시작점(루트)가 아닌 경우에는 자식에게서 return 받은 진입 순서의 최소값으로 판단
5. 코드
댓글 영역