개인적으로 그래프, 트리 등을 좋아하는 편이다. 이 알고리즘도 그래서 매우 재미있게 익힐 수 있었다.
강한 연결 요소는 DG (Directed Graph, 단방향 그래프)에서 사이클을 찾는 방법이다. 그리고 그 사이클은 포함할 수 있는 모든 정점을 최대한으로 포함시켜준다.
- 사이클을 이룰 수 있는 최대 크기 파악 가능 (하나의 사이클을 이루는 최대한 많은 정점 모두 포함)
- 사이클의 총 개수
- 사이클을 이루는 정점 번호
- 사이클을 하나의 정점으로 치환 후 위상정렬과의 연계
등등 다양한 기능을 수행한다.
본 포스팅에서는 코사라주 알고리즘으로 SCC를 찾아보겠다.
기본적인 방식은 DFS를 통해 하나의 정점에서 도달할 수 있는 최대한 먼 곳에서 가까운 순으로 번호를 달아주고,
역방향 그래프 상에서 다시 출발하여 같은 정점에 또 도달했다면 그 정점들은 사이클을 이룬다는 결론을 내는 것이다.
방향 그래프를 뒤집었으니, 도달하지 못해야하는데, 도달했다면 사이클이 있기 때문이라는 것이다. 어찌 보면 당연하게 받아들일 수도 있다.
여기서 중요한 것은 어디서 출발하느냐이다. 두번의 DFS를 돌아야 하는데, 첫 번째 DFS는 어디에서 출발해도 무방하다. (이 점이 매우 편리하다). 두 번째 DFS는 첫 번째 DFS에서 찾은 값중에서 가장 큰 값에서부터 시작하는 것이다.
아래의 그림을 보자.
5개의 정점이 놓여있다. 이중에서 1번에서 시작한다고 가정하자. 첫 번째 DFS는 더 이상 갈 수 없을 때까지 파고 들어가는 것이다. 위의 그래프에서는 5번까지 도달하면 5번에 num값을 기록할 것이다. 그리고 그 값은 0이나 1등 작은 수부터 쓴다. 그리고 ++을 통해 값을 키워둔다.
5번까지 가면 0을 쓰고, 그 다음에는 4에 1이 기록될 것이다. 이런 식으로 1까지 모두 값을 채우면 위와 같은 그림이 된다.
참고로, SCC는 간선이 아예 없어도 적용 가능하다. 일단 위의 그림에서는 num값이 클 수록 도달할 수 있는 정점들이 많은 것처럼 보인다. 5번 정점은 num값이 가장 작은 0이고, 더 이상 갈 곳이 아무 데도 없지만, 1번 정점은 num값이 4로 가장 크고 모든 정점에 도달할 수 있기 때문이다. 이는 사실일 수도 있다. 하지만, 조금 전에 언급했듯이, 간선이 아예 없다면 그냥 순서대로 num값을 배정받게 된다.
그래서 num값을 통해 어떠한 '사회성', '연결성' 등을 응용하고자 한다면, 아마도 모든 정점들이 연결되어있다는 조건과 그 외 몇가지 추가 조건이 필요할 것으로 보인다.
이제 두번째 DFS다. 아래 그림을 보자.
그래프는 뒤집어졌다. 간선을 빨간색으로 표시하여 역방향임을 강조했다. 이제 num값이 가장 큰 1번 정점에서 시작해야 하는데, 가장 큰 num값을 찾기 위해 일일이 모든 정점을 다시 다 훑어봐야 할까? 아니다. 첫 번째 DFS에서 num값을 기록할 때 스택에 넣어두면 된다. num값과 해당 정점을 묶어서 스택에 넣어두면, 스택의 특성상, 가장 작은 num값을 가진 정점이 바닥에 깔리게 된다. 그래서 위에서부터 뽑아서 쓰면 가장 큰 num값을 가진 정점부터 확인 가능해진다.
위의 그림에서와 같이, 1번 정점에서 시작하여 2와 3을 방문 가능하다. 즉, 이제 1, 2, 3은 사이클을 이룬다는 결론이 나온다.
그리고 이들을 묶어서 강한 연결 요소라고 부른다.
여기서 잠깐 다시 한번 더 생각해보자.
1에서 2사이에2 사이에 간선이 없었더라도, 1과 2는 num값을 받았을 것이다. 하지만 역방향 간선 그래프에서도 1과 2 사이에는 여전히 간선이 없으므로, 어디에서 시작해도 다른 정점에 도달할 수 없다.
그리고 1에서 2가 아닌 2에서 1로 가는 간선이었다면 배정받은 num값이 다를 것이다. 2가 더 큰 num값을 받았을 것이고, 역방향 그래프에서 2에서 출발하게 된다. 그리고 그때는 2에서 1로 갈 수 없을 것이다.
그래서 num값이 큰 정점에서부터 시작하여 DFS를 돌아야, 도달하는 정점들이 강한 연결요소를 이룬다는 결론을 낼 수 있는 것이다.
1차 DFS때, num값을 스택에 담았다면,
2차 DFS때는 출발점 포함, 도달하는 정점들을 모두 벡터나 리스트 등에 담아, 각 사이클을 이루는 정점들과 그 크기 등을 모두 알아낸다.
그리고 다른 미방문에서 다시 출발전에 벡터 리셋 등을 통해 한 그래프 내 사이클의 개수 등도 파악 가능하다.
사이클을 이루는 요소들을 하나의 정점으로 치환하면 DAG가 된다. (Directed Acyclic Graph)
그러면 이제 위상정렬 등 다른 알고리즘을 적용하여 여러 가지 응용이 가능해진다.
위의 그래프에서 보다시피, 1-2-3이 하나의 사이클, 4-5-6-7이 또 다른 사이클을 이루는 등으로 총 4개의 사이클이 있다. SCC알고리즘을 적용하면 이들을 모두 찾을 수 있게 된다. 그리고 그들을 묶어서 하나의 정점으로 치환하자.
그럼 이제 위와 같은 그림으로 바뀌고, 위상정렬을 통해 각 사이클의 방문순서까지 구할 수 있게 된다!
<주요 내용>
SCC, 강한 연결 요소, 역방향 그래프, 스택, 위상 정렬, 코사라주
<코드>
아래는 첫번째 DFS수행 코드이다. 방문 체크가 안되어있다면, 방문 체크 후에 다음 DFS로 파고들어간다.
그리고 더이상 갈 곳이 없을 때 num값을 기록하고, 스택에 넣고 빠져나온다.
stack<pair<int,int> > nums;
void DFS(int node){
if (!vis[node]){
vis[node] = 1;
for (int nx : graph[node])DFS(nx);
nums.push(make_pair(num, node));
numsRecord[node] = num;
num++;
}
}
그리고 다음은 두번째 DFS이다. 수행 전에 방문 체크 배열을 리셋해야 하는 점 주의한다.
vector<pair<int,int>> scc;
void sccSolve2(pair<int, int> p){
if (!vis[p.second]){
vis[p.second]=1;
scc.push_back(p);
for(int nx:graph_inv[p.second])sccSolve2(make_pair(numsRecord[nx], nx));
return;
}
}graph_inv는 역방향 그래프이다. 첫번째 DFS에서 사용한 그래프를 뒤집었다.
방문해가면서 자기자신도 포함하여 scc벡터에 넣어둔다. 그리고 계속 파고 들어간다.
재귀를 모두 나오고 나면 scc벡터에는 SCC를 이루는 정점들이 모두 들어있게 된다.
그리고 아직 방문하지 않은 정점들을 찾아 다른 사이클이 있는지 반복하면 된다.
아래의 연습 문제를 통해 더욱 개념을 다지자.
<연습 문제>
본 포스팅은 알고리즘의 대가이신 류호석님의 유튜브 동영상을 참조하여 만들었음을 밝힌다.
아래는 그 분의 동영상이다. (갓호석님으로부터 직접 허락을 받음)
www.youtube.com/watch?v=iKNkpiQhsE0&t=373s
