얼마 전에 후배에게 단절점과 SCC에 대한 질문을 받았는데 공부한지 오래되기도 했고 정리하는 시간이 필요할 거 같아서 글로 남기기로 하였다!
단절점은 우선 무향 그래프(Undirected Graph)에서 정의되는 개념이다.
단절점이란, 해당 정점을 그래프에서 지웠을 때 그래프의 전체 컴포넌트 수가 늘어나는 정점을 의미한다.
더 쉽고 풀어서 말해보자면 이쪽과 저쪽을 (혹은 그 이상을) 연결하는 점을 의미한다.
연결성을 중요하게 생각하는 상황에서(라우터의 연결을 나타낸 그래프 같은 거?) 단절점은 정말 중요한 점이다.
해당 정점에 (더 자세하게는 단절점에 연결된 간선이) 문제가 생긴다면 전체적인 연결 자체에 문제가 생긴다는 말이니까.
그렇다면 이 단절점은 어떻게 구할까?
제일 쉽고, 제일 빨리 생각나는 방법은 정점을 하나씩 지워보고 컴포넌트의 수가 늘어나는지 확인하는 것이다.
모든 정점에 대해서 BFS나 DFS를 사용한다면? 시간 복잡도는 O(N * (N + M))이 될 것이다. (N: 정점 갯수, M: 간선 갯수)
M은 최대 O(N^2)이기 때문에 최악의 경우에는 O(N^3)이 걸릴 것이다.
단절점에 대해 조금 더 생각해보자.
이해할 때 여러 레퍼런스를 참고하려고 했는데, (멍청한 내가) 이해하기에 그렇게 직관적이지 않아서 나름대로 직관적으로 설명해보려고 한다.
한 정점에서 DFS를 하게 되면 방문 순서가 매겨지게 된다.
이 방문 순서에 따라 트리 형태로 보게 되면 정점들 사이에 수직적인, 즉 어떤 정점은 부모, 어떤 정점은 자식이라는 '상대적'인 관계가 생기게 된다. (사실 DFS Spanning Tree를 그려보라는 말)
아까 위에서 단절점에 대한 설명을 해당 정점을 지웠을 때 전체 그래프에서 컴포넌트가 늘어나는 정점이라고 했다.
그리고 단절점이 연결에 있어서 없으면 안되는 중요한 역할을 하는 점이라고도 했다.
그렇다면 한 정점에서 자식 Subtree들이 그 정점을 거치지 않고도 그 정점보다 위에 있는 (더 빨리 방문한) 정점을 방문할 수 있다면, 그 정점은 연결에 있어서 중요하지 않은 점이다.
다시 말하면, 그 점이 없어도 다른 곳으로 돌아서 연결이 될 수 있다는 의미이므로, 연결에는 문제가 없다, 즉 컴포넌트의 갯수에는 차이가 없게 된다.
방금 전에, '자식 Subtree들이'라는 말을 했었는데, 이 문제를 재귀적으로 해결할 수 있는 이유이다.
자식 Subtree는 또 하나의 완전한 Tree로 볼 수 있다.
그렇다면, 그 트리에 대해서 같은 방법을 적용하고, 즉 leaf 노드로 갈 때까지 이 방법을 계속해 나가면 될 것이다.
하지만, 여기서 한가지 주의해야 할 점이 있다.
맨 처음에 우리가 DFS를 시작한 바로 그 정점이다.
이 정점의 자식 갯수가 두 개 이상이라면 이 정점은 단절점이다.
DFS를 시작한 점은 가장 높이 있는 Root 노드이기 때문에 이 점이 없어져 버리면 한 개의 컴포넌트가 자식의 갯수만큼으로 쪼개지게 된다.
이렇게 해서 단절점에 대한 설명을 마친다!
단절점에 대한 문제를 풀어보고 싶으면,
https://www.acmicpc.net/problem/11266
이해가 잘 안되시면 댓글로 질문해주세요 :)
