[그래프] 단절점, 단절선
단절점(Articulation Point), 단절선(Articulation Bridge) 구하기 (코틀린)
백준 단절점과 단절선 문제를 풀기 위해 단절점과 단절선에 대해 공부한 내용을 기록한다.
단절점
단절점 부터 알아보자. 단절점이 무엇일까?
하나의 컴포넌트(connected component)로 구성되어 있는 그래프에서 특정 정점을 제거할 때, 컴포넌트의 개수가 증가하는 정점을 단절점이라고 한다.
쉽게 말해, 어떤 정점을 제거했을 때 그래프가 둘 이상으로 나뉘게 된다면 그 정점은 단절점이라고 볼 수 있다.
단절점 조건
단절점이 되기 위해선 아래 2가지의 조건이 성립해야 한다.
- 정점 A보다 늦게 탐색 되는 정점들에서 정점 A보다 먼저 탐색 되는 정점으로 가는 경로가 없는 경우 정점 A는 단절점이다.
- 루트 노드로 잡은 특정 노드의 자식 수가 2개 이상이면 단절점이다.
위 조건들을 증명해보자. 아래와 같은 그래프가 있다.
위 그래프를 DFS Tree로 그려보면 아래와 같다.
위 트리에서 루트인 1번 노드를 없애보자.
루트 노드로 잡은 특정 노드의 자식 수가 2개 이상이면 단절점이다.
그럼 이렇게 그래프가 2개로 나뉘어지게 된다. 이로써 2번 조건은 증명했다. 1번 조건도 마저 증명해보자. 아래 그래프는 이해의 편의를 위해 노드의 키를 오름차순으로 변경하였다.
위 그래프에서 2번 노드를 없애보겠다.
정점 A보다 늦게 탐색 되는 정점들에서 정점 A보다 먼저 탐색 되는 정점으로 가는 경로가 없는 경우 정점 A는 단절점이다.
지운 2번 정점보다 늦게 탐색되는 정점인 3번 정점이, 지운 2번 정점보다 먼저 탐색되는 1번 정점으로 갈 수 있는 간선이 3–1로 존재하므로 그래프의 갯수가 변함이 없다. 따라서 2번 정점은 단절점이 아니다.
이번엔 5번 정점을 없애보자.
정점 A보다 늦게 탐색 되는 정점들에서 정점 A보다 먼저 탐색 되는 정점으로 가는 경로가 없는 경우 정점 A는 단절점이다.
지운 5번 정점보다 늦게 탐색되는 정점 6, 7번이, 지운 5번 정점보다 더 먼저 탐색되는 4번 정점으로 갈 수 있는 간선이 없다. 따라서 그래프가 총 3개로 나뉘어졌고, 5번 정점은 단절점이 맞다.
이렇게 단절점이 성립하는 조건에 대해 알아봤다. 이제 주어진 그래프에서 단절점을 구해보자.
단절점 구하기
단절점은 전 아티클에서 소개한 타잔 알고리즘을 통해 구할 수 있다. 아래 문제로 예를 들어보자.
단절점을 구하는 아주 기본적인 문제다. 위 문제는 아래 코드를 통해 해결할 수 있다.
단절선
위에서 단절점에 대해 알아봤다. 이제 단절선에 대해 알아보자.
단절선이 무엇일까? 단절점과 비슷하다.
하나의 컴포넌트(connected component)로 구성되어 있는 그래프에서 특정 간선을 제거할 때, 컴포넌트의 개수가 증가하는 간선을 단절선이라고 한다.
쉽게 말해, 어떤 간선을 제거했을 때 그래프가 둘 이상으로 나뉘게 된다면 그 간선은 단절선이라고 볼 수 있다.
단절선 조건
단절선이 되기 위해선 아래 조건이 성립해야 한다.
- 현재 정점 A와 자식 정점 B를 잇는 간선 A-B에서, A의 자식들 중 A를 거치치 않고 A 이전에 방문했던 정점에 갈 수 없다면 간선 A-B는 단절선이다.
위 조건을 증명해보자. 아래와 같은 그래프가 있다. (단절점 설명과 같은 그래프)
위 그래프를 DFS Tree로 그려보면 아래와 같다. (이해의 편의를 위해 노드의 키를 오름차순으로 변경하였다)
위 트리에서 2–3 간선을 지워보자.
현재 정점 A와 자식 정점 B를 잇는 간선 A-B에서, A의 자식들 중 A를 거치치 않고 A 이전에 방문했던 정점에 갈 수 없다면 간선 A-B는 단절선이다.
지운 2–3 간선 없이도, 2번 정점보다 먼저 나오는 1번 정점에 3–1 간선으로 갈 수 있다. 따라서 그래프의 갯수가 변함이 없으므로 2–3 간선은 단절선이 아니다.
이번엔 4–5간선을 없애보자.
현재 정점 A와 자식 정점 B를 잇는 간선 A-B에서, A의 자식들 중 A를 거치치 않고 A 이전에 방문했던 정점에 갈 수 없다면 간선 A-B는 단절선이다.
4–5 간선을 없애니, 4번 정점보다 먼저 나오는 1번 정점에 5번 정점에서 갈 수 있는 간선이 없다. 따라서 그래프가 2개로 나뉘어지고, 4–5 간선은 단절선이 맞다.
이렇게 단절선이 성립하는 조건에 대해 알아봤다. 이제 주어진 그래프에서 단절선을 구해보자.
단절선 구하기
단절선도 마찬가지로 전 아티클에서 소개한 타잔 알고리즘을 통해 구할 수 있다. 아래 문제로 예를 들어보자.
단절선을 구하는 아주 기본적인 문제다. 위 문제는 아래 코드를 통해 해결할 수 있다.
번외) 트리 관점에서 보는 단절점과 단절선
지금까지 그래프 관점에서 단절점과 단절선에 대해 알아봤다.
하지만 트리에서는 어떨까? 아래 문제를 보자.
위 문제에서 위 그래프 처럼 DFS로 단절점과 단절선을 구하면 시간 초과가 뜬다. 트리 관점에서의 단절점과 단절선은 트리의 성질을 이용하면 쉽게 알아낼 수 있다.
- 트리는 사이클이 없기 때문에 연결된 간선이 2개 이상이면 단절점이다.
- 트리는 사이클이 없기 때문에 모든 선이 단절선이다.
위 성질을 이용하며 아래와 같이 간단하게 코드를 짤 수 있다.
끝!
골드5 문제 하나를 풀기 위해, 플레5 문제 3개를 풀었다. 신기한 난이도 시스템…
