전국을 거미줄처럼 잇는 통신 네트워크나 도로망이 있습니다. 테러리스트가 이 네트워크를 마비시키기 위해 단 하나의 기지국(노드)이나 단 하나의 도로(간선)만 폭파시켜도 전체 네트워크가 두 동강이 나버리는 '단일 장애점(Single Point of Failure)'을 찾는다면 어디일까요? 그래프 이론에서는 이를 단절점(Articulation Point)과 단절선(Bridge)이라고 부릅니다. 이 치명적인 약점을 찾기 위해 모든 노드를 한 번씩 지워보고 그래프가 끊어지는지 일일이 BFS/DFS로 확인한다면 O(V * (V+E))의 끔찍한 시간이 소요됩니다. 하지만 타잔(Tarjan)이 고안해 낸 DFS 스패닝 트리와 우회로 탐색 기법을 사용하면, 그래프를 단 한 번 훑는 O(V+E)의 선형 시간 만에 모든 단절점과 단절선을 완벽하게 색출해 낼 수 있습니다.
1. 우회로가 없는 치명적인 약점
단절점의 핵심 논리는 매우 직관적입니다. "나를 거치지 않고서는, 내 자식들이 내 조상(과거 방문했던 노드)에게 도달할 수 있는 우회로(Back Edge)가 전혀 존재하지 않는다"면, 나는 그들을 이어주는 유일한 생명줄이므로 단절점이 됩니다. 반대로 자식 중 단 하나라도 나를 거치지 않고 조상과 연결된 샛길을 가지고 있다면, 내가 폭파되어도 그 샛길로 통신하면 되므로 나는 단절점이 아닙니다.
2. DFS 스패닝 트리와 방문 순서(Discovered)의 마법
이를 구현하기 위해 아무 노드에서나 DFS(깊이 우선 탐색)를 시작하고, 방문하는 순서대로 노드에 고유 번호(discovered 시간)를 1번부터 차례대로 매깁니다.
2-1. Low-link 값의 도출
탐색 중인 각 노드는 두 가지 중요한 값을 가집니다.
discovered[node]: 내가 DFS를 통해 처음 방문된 순서 번호low[node]: 나와 내 자손들이 정상적인 트리 간선 및 우회로(Back Edge)를 모두 포함해서 도달할 수 있는 노드들 중, 가장 번호가 작은(가장 오래된 조상의) 방문 번호
DFS가 자식 노드들을 다 방문하고 되돌아올 때(Backtrack), 자식들의 low 값을 끌어올려 나의 low 값을 갱신합니다. 만약 어떤 자식 노드 v가 탐색을 마치고 내놓은 최소 도달 번호 low[v]가, 나의 방문 번호 discovered[u]보다 크거나 같다면? 이는 자식 v의 무리들이 아무리 발버둥 쳐도 나(u)를 통과하지 않고서는 나보다 위쪽에 있는 조상으로 갈 수 없다는 사망 선고를 의미합니다. 즉, 이 순간 나(u)는 단절점으로 확정됩니다.
단절선(Bridge)도 원리는 똑같습니다. 자식 v의 low[v]가 내 번호 discovered[u]보다 무조건 크다면(같아도 안 됨), 나와 자식을 잇는 그 간선은 유일한 다리이므로 단절선이 됩니다.
3. 루트(Root) 노드의 특별한 예외 처리
위의 공식을 그대로 적용하면, DFS를 맨 처음 시작한 루트 노드는 항상 low[v] >= discovered[u]를 만족해 버리므로 무조건 단절점이라는 오판을 내리게 됩니다. 따라서 루트 노드에 대해서만 특별한 예외 규칙을 적용해야 합니다.
루트 노드는 자신보다 더 높은 조상이 아예 존재하지 않습니다. 따라서 우회로 여부와 상관없이, 루트 노드가 단절점이 되기 위한 유일한 조건은 "DFS 스패닝 트리 상에서 자식 트리가 2개 이상 있는가?"입니다. 자식이 1개뿐이라면 루트가 없어져도 밑에 있는 녀석들끼리 잘 살아남으므로 단절점이 아닙니다. 이 예외 처리까지 완벽히 마친다면, 어떠한 복잡한 그래프에서도 네트워크의 아킬레스건을 단숨에 찾아낼 수 있습니다.
1. 단절점(Articulation Point)과 단절선(Bridge)은 제거했을 때 그래프가 두 개 이상의 컴포넌트로 쪼개지는 치명적인 핵심 노드와 간선을 뜻합니다.
2. 모든 정점을 DFS로 순회하며 방문 순서를 기록하고, 내 자손들이 우회로를 통해 도달할 수 있는 가장 높은 조상의 번호(
low 값)를 갱신합니다.3. 자식의
low 값이 내 방문 번호보다 크거나 같으면 나는 단절점, 자식의 low 값이 내 방문 번호보다 크면 그 간선은 단절선이 되며, 탐색은 단 한 번의 $O(V+E)$만 소요됩니다.