복잡하게 얽혀 있는 도로망이나 웹페이지의 하이퍼링크 네트워크, 혹은 사용자 간의 팔로우 관계를 나타내는 방향 그래프(Directed Graph)를 분석할 때, 네트워크 학자들이 가장 중요하게 살펴보는 개념이 있습니다. 바로 그래프 내부에서 "어떤 노드에서 출발하더라도 나머지 모든 노드로 찾아갈 수 있고, 또다시 자기 자신으로 돌아올 수 있는 가장 거대한 폐쇄적 무리"를 찾는 것입니다. 이러한 노드들의 끈끈한 집합을 컴퓨터 공학에서는 강한 연결 요소(Strongly Connected Component, 이하 SCC)라고 부릅니다. 거대한 그래프를 여러 개의 유의미한 그룹(클러스터)으로 분해하여 전체 시스템의 뼈대를 파악하는 핵심 기술입니다. 이 SCC를 O(V+E)의 압도적인 선형 시간에 추출해 내는 두 명의 천재, 코사라주(Kosaraju)와 타잔(Tarjan) 알고리즘의 원리를 비교하며 완벽하게 정리해 봅니다.
1. 강한 연결 요소(SCC)의 정확한 정의
방향 그래프가 주어졌을 때, 그래프 내의 어떤 부분 집합에 속한 임의의 두 정점 U와 V를 골랐을 때, U에서 V로 가는 경로가 존재하고 동시에 V에서 U로 가는 경로도 100% 존재하는 집합을 강한 연결 요소(SCC)라고 정의합니다. 쉽게 말해, 방향성을 무시하지 않고도 그 집합 안에서는 모든 노드가 서로 빙글빙글 돌며 상호 도달이 가능한 하나의 거대한 '순환 고리(Cycle)'를 형성하고 있다는 뜻입니다. SCC 알고리즘의 궁극적인 목표는 전체 그래프를 이 SCC 덩어리 단위로 예쁘게 잘라내어 그룹핑(Grouping)하는 것입니다.
2. 코사라주 알고리즘 (Kosaraju's Algorithm): 직관의 승리
코사라주 알고리즘은 논리 구조가 매우 직관적이고 이해하기 쉬워 코딩 테스트에서 주로 선호되는 방식입니다. '순방향 DFS'와 '역방향 DFS', 총 두 번의 DFS(깊이 우선 탐색)를 수행하여 SCC를 발라냅니다.
2-1. 코사라주의 3단계 탐색 과정
- 정방향 DFS와 스택(Stack): 그래프의 임의의 정점에서 DFS 탐색을 시작합니다. 더 이상 탐색할 곳이 없어 해당 노드의 DFS 함수가 완전히 종료(Return)되는 순간, 그 노드의 번호를 준비해 둔 스택(Stack)에 차곡차곡 쌓아둡니다(Push). 이 과정은 그래프 전체를 순회할 때까지 진행됩니다.
- 역방향 그래프(Reverse Graph) 생성: 원본 그래프의 모든 간선(화살표)의 방향을 완전히 반대로 뒤집은 새로운 그래프를 하나 만듭니다. SCC 내부의 노드들은 어차피 둥글게 순환하므로 방향을 싹 다 뒤집어도 여전히 상호 도달이 가능하다는 수학적 성질을 이용한 것입니다.
- 역방향 DFS로 무리 짓기: 이제 1단계에서 쌓아두었던 스택에서 노드를 하나씩 꺼냅니다(Pop). 꺼낸 노드를 시작점으로 삼아, 방금 만든 역방향 그래프 위에서 다시 한번 DFS를 수행합니다. 이때 한 번의 DFS 호출로 인해 탐색되면서 방문 처리되는 모든 노드들의 묶음이 바로 하나의 거대한 SCC 덩어리가 됩니다!
3. 타잔 알고리즘 (Tarjan's Algorithm): 한 번의 탐색으로 끝내다
타잔 알고리즘은 코사라주와 달리 역방향 그래프를 만들지 않고, 단 한 번의 DFS 탐색만으로 모든 SCC를 찾아내는 극도로 세련된 방식을 사용합니다. 논리가 약간 복잡하지만, 데이터 전처리 오버헤드가 없어 실측 속도는 미세하게 더 빠릅니다.
3-1. 부모로 거슬러 올라가는 'Low-Link'의 마법
타잔 알고리즘은 DFS를 수행하면서, 각 노드마다 자신이 몇 번째로 방문되었는지 나타내는 '방문 순서(Discovery Time)' 고유 번호를 매깁니다. 그리고 동시에 현재 노드에서 출발하여 (자식들을 거쳐) "자신보다 방문 순서가 더 빠른 과거의 노드로 거슬러 올라갈 수 있는지(역방향 간선, Back Edge)"를 계산하여 최솟값(Low-Link Value)을 기록합니다.
- DFS를 진행하며 방문하는 모든 노드를 임시 스택(Stack)에 밀어 넣습니다.
- 만약 어떤 노드
U의 Low-Link 값이 자신의 고유 방문 순서 번호와 정확히 일치한다면, 이는 자신이 속한 순환 고리(Cycle)에서 자신이 가장 꼭대기(루트)에 있는 대장 노드라는 뜻이 됩니다. (나보다 더 위로 올라갈 샛길이 없다는 의미입니다.) - 대장 노드를 발견한 즉시, 임시 스택에서 대장 노드
U가 튀어나올 때까지 데이터를 계속 Pop 하여 꺼냅니다. 이 꺼내어진 노드들의 무리가 바로 완벽한 하나의 SCC가 됩니다.
1. 강한 연결 요소(SCC)는 방향 그래프 내에서 모든 정점이 서로 도달 가능한 거대한 순환 집합체(클러스터)를 의미합니다.
2. 코사라주(Kosaraju) 알고리즘은 스택에 종료 순서를 기록한 뒤, 간선을 모두 뒤집은 역방향 그래프에서 다시 DFS를 돌려 직관적이고 깔끔하게 SCC를 추출해 냅니다.
3. 타잔(Tarjan) 알고리즘은 단 한 번의 DFS 과정 중, 부모로 거슬러 올라갈 수 있는 최소 경로(Low-Link)를 계산하여 스택을 비워내는 방식으로 SCC를 묶어내는 최적화 기법입니다.