직장인의 개발 일기

1. 단절점(Articulation Point)이란?

단절점이란 그 정점을 제거했을 때, 그래프가 두 개 또는 그 이상으로 나누어지는 정점을 말한다. 즉, 제거했을 때 그래프의 connected component의 개수가 증가하는 정점을 말합니다.

2. 단절점(Articulation Point)동작 원리?

dfs를 활용하여 O(V+E)의 시간복잡도로 문제를 해결할 수 있습니다.

위 그래프의 방문 순서에 따라 id값을 매깁니다. id값은 1부터 시작하여 1씩 증가합니다. 방문 순서는 1→3→4→5→2→6이 됩니다.

방문하지 않은 노드를 방문할 때마다 dfs를 수행하여 단절점을 확인해보겠습니다.

단절점의 발견 조건은 특정 i번 노드에서 자식 노드들이 노드 i를 거치지 않고 노드 i보다 낮은 id값을 가진 노드로 갈 수 없다면 단절점입니다. 또한 현재 노드가 루트 노드일 때 자식 노드가 2개 이상이라면 단절점입니다.

4번과 5번 노드는 3번 노드를 거치지 않으면 1번 노드로 가지 못합니다. 따라서 3번 노드는 단절점입니다.

위와 같은 방법으로 2번 노드와 6번 노드는 5번 노드를 거쳐야하고, 6번 노드는 2번 노드를 거쳐야하므로 2번 노드와 5번 노드 또한 단절점입니다.