그래프 문제를 많이 풀어본 건 아니지만, 다익스트라나 프림 같은 유명한 알고리즘이나 DFS로 방문 체크(문제 시작은 항상 똑같은 이름에만 하면 "결국 최단거리, 가중치 최소/최대, 아니면 사이클 찾는 문제들?" 대부분 풀릴거라 생각했다.visited[] 만들기)
하지만 복잡하게 얽힌 '방향 그래프'라면 어떨까? 단순히 사이클이 있냐 없냐를 넘어, 사이클들이 구조적으로 어떤 관계를 맺고 있는지 파악해야 한다면? 그때는 단순한 탐색만으로는 한계에 부딪힌다.
이번 BOJ. 텀 프로젝트 문제를 풀면서 SCC(Strongly Connected Components, 강한 연결 요소)를 알게 되었다.
오늘은 내가 단순한 사이클 탐색에서 시작해 왜 SCC라는 개념까지 도달하게 되었는지, 어떻게 다른지 정리해보려 한다.
알고 있던 그래프 알고리즘은 어떻게 사이클을 다뤘을까?
다익스트라(Dijkstra)
다익스트라의 목적은 오로지 최단 거리
사이클이란 존재하든 말든 상관없는 대상이다.
양수 가중치를 가진 사이클이라면 굳이 뱅뱅 돌 이유가 없으니 최단 경로에서 자연스럽게 고려대상이 안된다.
오직 음수 사이클만이 무한히 비용이 작아지는 문제를 일으키기 때문에 예외로 취급될 뿐
프림(Prim) & 크루스칼(Kruskal)
이들의 목적은 최소 신장 트리(MST)를 만드는 것
트리의 정의 자체가 '사이클이 없는 그래프'이기 때문에,
여기서 사이클은 제거해야 할 대상이다.
간선을 연결하다가 사이클이 만들어질 것 같으면 그 간선은 과감히 버린다.
사이클이 '누구'인지가 중요할 때
사이클이 있냐 없냐가 중요한 게 아니라, 어떤 노드들이 사이클을 구성하는지 얼마나 뭉쳐있는지
이 때, 단순한 DFS 탐색과 SCC의 차이가 발생
예시: 텀 프로젝트 (백준 9466)
학생들이 팀을 이루는데, 서로가 서로를 지목해서 사이클이 형성되어야만 팀이 결성되는 문제다.
- DFS 기반 사이클 탐색으로 풀이한 코드
import sys
input = sys.stdin.readline
tc = int(input())
for _ in range(tc):
n = int(input())
arr = [0] + list(map(int, input().split()))
visited = [0] * (n + 1)
cnt = 0
for i in range(1, n + 1):
if visited[i] != 0:
continue
# 경로 탐색 시작
now = i
while True:
# 방문 표시를 현재 시작점 i로 설정
visited[now] = i
now = arr[now]
# 만일 방문했던 곳을 다시 만나면?
if visited[now] == i:
# 이번 방문이 이전에 방문했던(i)라면? -> 사이클!
while visited[now] != -1:
# 사이클 처리
visited[now] = -1
cnt += 1
now = arr[now]
break
# 이미 이전에 처리한 사이클 노드라면?
elif visited[now] != 0:
break
# 사이클에 포함되지 못한 경로
now = i
while visited[now] == i:
visited[now] = -1
now = arr[now]
print(n - cnt)각 노드의 진출 차수가 딱 1개이기 때문에,
그래프는 무조건 꼬리 -> 사이클 형태를 띤다.
여기서 핵심 로직은 visited[now] == i
"내가 지금 탐색하고 있는 경로에서 다시 나를 만났다"는 것은 사이클을 찾았다는 뜻
이 풀이는 '경로를 따라가며 확인'하는 방식이지, 구조를 파악하지는 않는다. 이왕 SCC를 알아보기로 한거 SCC를 사용하여 다시 풀어보자!
구조적 접근: SCC (Strongly Connected Components)
SCC의 정의
방향 그래프에서 어떤 노드 집합을 골랐을 때, 그 안의 모든 노드 쌍 (A, B)에 대해 A에서 B로 가는 경로도 있고, B에서 A로 가는 경로도 있다면 이 집합을 강한 연결 요소(SCC)라고 부른다.
사이클과 SCC의 관계
- 단순한 사이클(1->2->3->1)은 그 자체로 하나의 SCC다.
- 하지만 사이클 여러 개가 얽혀 있거나, 복잡하게 꼬여 있을 때 이들을 하나의 덩어리로 묶어주는 개념이 바로 SCC다.
SCC 단위로 그래프를 압축하면, 그래프는 사이클이 없는 DAG(방향 비순환 그래프) 형태가 된다. 즉, 복잡한 그래프 문제를 "큰 덩어리들의 순서 문제"로 단순화시킬 수 있게 되는 것이다.
SCC를 구하는 두 가지 방법
SCC를 구하는 알고리즘은 크게 코사라주(Kosaraju)와 타잔(Tarjan) 두 가지가 있다. 둘 다 시간 복잡도는 로 동일하지만, 접근 방식과 구현 스타일에서 차이가 있다.
1) 코사라주 알고리즘 (Kosaraju)
"방향을 뒤집어도 묶여있는 애들은 여전히 묶여있다"는 성질을 이용한다.
- 정방향 DFS: 그래프를 탐색하며 빠져나오는 순서(종료 시간)를 스택에 추가한다.
- 역방향 그래프: 모든 간선의 방향을 뒤집는다.
- 역방향 DFS: 스택에서 하나씩 꺼내면서 역방향 그래프를 탐색을 진행, 이때 한 번의 탐색으로 묶이는 노드들이 하나의 SCC가 된다.
구현은 DFS를 두 번 돌리면 되기 때문에 크게 어렵지 않다.
ALGORITHM KosarajuSCC(Nodes N, Graph G)
INPUT: 노드 개수 N, 인접 리스트 G
OUTPUT: 강한 연결 요소(SCC)들의 리스트
// 1. 정방향 DFS 탐색 (종료 순서 기록)
Stack S = empty
Visited[] = {False, ...}
FUNCTION DFS_Forward(u):
Visited[u] = True
FOR each neighbor v in G[u]:
IF Visited[v] is False:
DFS_Forward(v)
// 탐색이 끝난 순서대로 스택에 저장
S.push(u)
FOR i from 1 to N:
IF Visited[i] is False:
DFS_Forward(i)
// 2. 그래프 뒤집기 (역방향 그래프 생성)
ReverseGraph RG = empty
FOR u from 1 to N:
FOR each neighbor v in G[u]:
Add edge (v -> u) to RG
// 3. 역방향 DFS 탐색 (SCC 추출)
// 방문 배열 초기화
Visited[] = {False, ...}
SCC_List = empty
FUNCTION DFS_Backward(u, current_component):
Visited[u] = True
Add u to current_component
FOR each neighbor v in RG[u]:
IF Visited[v] is False:
DFS_Backward(v, current_component)
WHILE S is not empty:
// 종료 순서가 늦은 노드부터 꺼냄
node = S.pop()
IF Visited[node] is False:
Component = empty
DFS_Backward(node, Component)
Add Component to SCC_List
RETURN SCC_List2) 타잔 알고리즘 (Tarjan)
코사라주보다 개념은 조금 더 어렵지만, DFS를 딱 한 번만 수행하면 된다.
- DFS를 돌며 각 노드에 방문 순서(id)를 매긴다.
- 스택을 이용해 "내 조상(부모)으로 되돌아갈 수 있는가?"를 확인한다.
low-link값이 자기 자신의 방문 순서와 같다면, 그 노드가 SCC의 '뿌리'가 되어 스택에 쌓인 자식들을 묶어낸다.
ALGORITHM TarjanSCC(Nodes N, Graph G)
INPUT: 노드 개수 N, 인접 리스트 G
OUTPUT: 강한 연결 요소(SCC)들의 리스트
// 전역 변수 초기화
IDs[] = {0, ...} // 방문 순서 (d 배열)
Finished[] = {False, ...} // SCC 처리 완료 여부
Stack S = empty // 탐색 중인 경로 저장
SCC_List = empty
ID_Counter = 0 // 방문 순서 카운터
FUNCTION DFS(u):
ID_Counter = ID_Counter + 1
IDs[u] = ID_Counter
S.push(u)
// 자신의 LowLink(최소 도달 가능 ID)를 자신의 ID로 초기화
LowLink = IDs[u]
FOR each neighbor v in G[u]:
IF IDs[v] is 0: // 1. 아직 방문하지 않은 노드
ChildLowLink = DFS(v)
LowLink = min(LowLink, ChildLowLink)
ELSE IF Finished[v] is False: // 2. 방문했으나 처리 안 됨 (스택에 있음 = 사이클)
LowLink = min(LowLink, IDs[v])
// SCC 추출 자신이 SCC의 루트(조상)인 경우
IF LowLink == IDs[u]:
CurrentSCC = empty
REPEAT:
node = S.pop()
Finished[node] = True
Add node to CurrentSCC
UNTIL node == u
Add CurrentSCC to SCC_List
RETURN LowLink
// 메인 실행 루프
FOR i from 1 to N:
IF IDs[i] is 0:
DFS(i)
RETURN SCC_ListTip: 코사라주는 구현이 직관적이라 코딩 테스트 중 "시간이 충분하고 머리가 복잡할 때" 쓰기 좋고, 타잔은 라이브러리처럼 외워두고 "빠르고 간결하게" 짤 때 좋다.
BOJ. 텀 프로젝트 문제를 타잔 알고리즘으로 본다면?
-
DFS기반 사이클 탐색: 경로를 따라가다가 "어? 아까 본 애네?" 하고 사이클을 감지
-
SCC 풀이: 그래프 전체를 SCC로 분해 후, SCC의 크기가 2 이상이거나, 크기가 1이면서 자기 자신을 가리키는 경우만 '팀 구성 완료(사이클)'로 판단
import sys
input = sys.stdin.readline
T = int(input())
for _ in range(T):
n = int(input())
arr = [0] + list(map(int, input().split()))
d = [0] * (n + 1) # 방문 순서 (id)
finished = [False] * (n + 1) # SCC 확정 여부
scc_stack = [] # 노드를 담을 스택 (역방향)
id_counter = 0
cnt = 0 # 팀을 이룬 학생 수
# 1번부터 n번 학생까지 순회
for i in range(1, n + 1):
# 이미 방문했다면 패스
if d[i] != 0:
continue
# 정방향 탐색
# 재귀 대신 path 리스트에 이동 경로를 기록
path = []
curr = i
while True:
# 방문 처리 및 스택 등록
id_counter += 1
d[curr] = id_counter
scc_stack.append(curr)
path.append(curr)
# 다음 이동할 노드
next_node = arr[curr]
# 다음 노드가 이미 방문된 경우 (사이클 or 이미 끝난 SCC 만남)
if d[next_node] != 0:
break
curr = next_node
"""
역방향 탐색 (Backtracking & SCC 추출)
path를 거꾸로 거슬러 올라가며 low-link를 갱신
만약 다음 노드가 '방문은 했는데 처리가 안 된(스택에 있는)' 상태라면
그 노드의 d값으로 초기 low_link를 설정 (사이클 발견)
이미 처리가 끝난(finished) 노드라면 연결이 끊긴 것으로 간주 (무한대 취급)
"""
next_node = arr[path[-1]]
if not finished[next_node]:
parent_low = d[next_node]
else:
parent_low = float('inf')
# 경로를 역순으로(자식 -> 부모) 올라가며 처리
while path:
u = path.pop()
# low_link 갱신(내 번호 vs 자식들이 도달 가능한 가장 높은 번호)
low_link = min(d[u], parent_low)
# SCC 루트 발견 (내 low_link가 내 방문번호와 같음)
if low_link == d[u]:
current_scc_size = 0
while True:
t = scc_stack.pop()
finished[t] = True
current_scc_size += 1
if t == u:
break
# 팀 판별 (사이클 크기가 2 이상이거나, 혼자서 자기를 찍은 경우)
if current_scc_size > 1:
cnt += current_scc_size
elif arr[u] == u:
cnt += 1
# SCC가 끊겼으므로 부모에게 전달할 low값은 무한대(연결 안됨)로 초기화
parent_low = float('inf')
else:
# SCC가 아니면 내 low_link를 부모에게 그대로 전달
parent_low = low_link
# 전체 학생 수 - 팀에 속한 학생 수
print(n - cnt)마무리
단순히 "사이클이 있다/없다"를 판별하는 문제라면 DFS 하나로 충분하다.
하지만 "어떤 노드들이 하나의 구조를 이루고 있는가?"를 물어보는 문제라면, 그때는 SCC가 필요하다.
다익스트라와 프림이 '비용 (가중치)'을 최소화하기 위한 알고리즘이라면, SCC는 그래프의 '구조'를 파악하고 단순화하기 위한 알고리즘이다.
참고: 최단거리 시뮬레이션
