SCC 알고리즘는 이름만 보고 판단하면 핵심을 놓치기 쉬운 주제입니다. 이 글은 최신 출처와 구조를 기준으로 독자가 실제로 확인해야 할 기준을 정리합니다.
핵심은 방향 그래프에서 서로 도달 가능한 그룹을 찾는 SCC 이해입니다. 단정적인 결론보다 확인 순서와 리스크를 분리해 보는 것이 중요합니다.
SCC 알고리즘 흐름을 그림으로 보기
SCC 알고리즘은 무엇을 묶는가
SCC 알고리즘은 방향 그래프에서 서로 오갈 수 있는 정점들을 하나의 그룹으로 묶습니다. 무방향 그래프의 연결 요소와 비슷해 보이지만, 방향 그래프에서는 ‘갈 수 있다’와 ‘돌아올 수 있다’가 모두 필요합니다.
핵심은 A에서 B로 갈 수 있고 B에서도 A로 돌아올 수 있을 때 같은 SCC가 될 수 있다는 점입니다.
방향 그래프에서는 연결이라는 말이 더 까다롭다
무방향 그래프에서는 선이 이어져 있으면 같은 연결 요소로 묶기 쉽습니다. 하지만 방향 그래프에서는 A에서 B로 가는 간선이 있어도 B에서 A로 돌아오는 길이 없을 수 있습니다.
그래서 SCC는 단순히 이어져 있는 묶음이 아니라 서로 도달 가능한 묶음입니다. 이 조건 때문에 한 방향으로만 흐르는 그래프는 여러 SCC로 쪼개질 수 있습니다.
Kosaraju 알고리즘 흐름
- 원래 그래프에서 DFS를 돌며 각 정점의 종료 순서를 기록한다
- 모든 간선 방향을 뒤집은 역방향 그래프를 만든다
- 종료 순서가 늦은 정점부터 역방향 그래프에서 DFS를 시작한다
- 한 번의 DFS로 방문되는 정점들이 하나의 SCC가 된다
처음 보면 왜 간선을 뒤집는지 이상해 보입니다. 종료 순서는 그래프의 큰 흐름에서 나중에 닫히는 덩어리를 알려주고, 역방향 그래프 DFS는 그 덩어리 안에서 되돌아갈 수 있는 정점들을 모아줍니다.
작은 코드 예시
vector<vector> g, rg;
vector order, comp;
vector visited;
void dfs1(int v) {
visited[v] = 1;
for (int nxt : g[v]) {
if (!visited[nxt]) dfs1(nxt);
}
order.push_back(v);
}
void dfs2(int v, int cid) {
comp[v] = cid;
for (int nxt : rg[v]) {
if (comp[nxt] == -1) dfs2(nxt, cid);
}
}
int kosaraju(int n) {
visited.assign(n, 0);
comp.assign(n, -1);
for (int i = 0; i < n; i++) {
if (!visited[i]) dfs1(i);
}
reverse(order.begin(), order.end());
int cid = 0;
for (int v : order) {
if (comp[v] == -1) {
dfs2(v, cid++);
}
}
return cid;
}SCC를 찾고 나면 무엇이 좋아질까
SCC를 찾으면 복잡한 방향 그래프를 덩어리 단위로 압축할 수 있습니다. 같은 SCC 안에서는 서로 도달 가능하므로 하나의 큰 정점처럼 볼 수 있습니다.
이렇게 압축한 그래프를 condensation graph라고 부르며, 이 그래프는 사이클이 없는 DAG가 됩니다. 그래서 이후 위상 정렬이나 의존성 분석으로 이어질 수 있습니다.
언제 SCC를 떠올릴까
- 서로 도달 가능한 그룹을 묻는 문제
- 방향 그래프에서 순환 구조를 묶어야 하는 문제
- 그래프를 압축한 뒤 DAG로 처리해야 하는 문제
- 2-SAT처럼 강한 연결 요소가 핵심 조건으로 쓰이는 문제
정리
SCC는 방향 그래프에서 서로 오갈 수 있는 정점들을 묶는 도구입니다. DFS 자체보다 중요한 감각은 방향 때문에 연결의 의미가 달라진다는 점입니다. 이 감각을 잡으면 SCC, 위상 정렬, 2-SAT 같은 심화 그래프 문제로 넘어가기가 훨씬 쉬워집니다.
관련 글로는 DFS와 BFS 차이, 위상 정렬은 왜 DAG에서만 가능할까, 그래프 입력 인접 리스트와 인접 행렬을 함께 보면 좋습니다. 외부 기준은 cp-algorithms – Strongly Connected Components, Wikipedia – Strongly connected component을 확인했습니다.
