#SCC #그래프이론 #DFS #코사리주 알고리즘
Strongly Connected Component(이하 SCC) 는 특정 그룹에서 뽑은 두 노드 A,B 에서 A->B 로 향하는 경로가 항상 존재하면 해당 그룹을 SCC 라고 칭한다.
<SCC 의 조건이자 룰이 두 가지 정도있다>
- 같은 SCC 그룹 내에 서로 다른 두 노드 간의 경로가 항상 존재해야함.
- 서로 다른 SCC 그룹 내에서 노드 한 개씩 뽑아서 A,B 노드라고 하면 A->B 가 존재하면 B->A 는 존재하면 안된다. 그룹 간의 사이클을 없앤다.
위 사진은 방향 그래프 내에서 SCC 그룹을 표시한 것이다.
SCC 를 다룬다는 것은 주로 SCC 그룹찾기(그룹 안의 노드 출력하기), SCC 그룹 수 찾기 등등에 쓰인다.
SCC 를 찾기, 탐색 하기 위해서 쓰는 알고리즘이 두 가지 있는데 그 중에서 코사리주 알고리즘을 정리해본다.
코사리주 알고리즘
코사리주 알고리즘은 DFS 를 두 번 하여 SCC 그룹들을 찾는다.
- 첫 번째 DFS : 방문순서대로 stack 에 노드를 차곡차곡 쌓는 과정
- 두 번째 DFS : stack 에 쌓은 역순으로 노드를 역으로 탐색하여 최종적인 SCC 를 찾는과정
코사리주 알고리즘 - 첫 번째 DFS
위 그래프를 탐색해서 SCC 를 찾아보자.
DFS 를 시작한다.
처음에는 0 번 노드부터 탐색한다. 탐색할 때마다 현재 노드를 visited 체크하므로 0번, 1번, 2번, 3번 노드는 차례대로 visited 처리 될 것이다. 이제 3번 노드에서 0번노드를 가려고 할 때, 0 번 노드는 visited 체크가 되어있으므로 3번은 갈 곳이 없이 stack 에 push 된다.
그리고 2번 노드로 돌아와서, 2 번 노드에서는 3 번 노드 말고도 4 번노드로 갈 수 있는 길이 아직 열러있다. 그러므로 아직 stack 에 넣지 않겠다.
방향을 따라 4 번, 5 번, 6 번, 7 번 노드까지 탐색을 한다. 7 번에서는 더 이상 갈 곳이 없는 처지 이므로 stack 에 push 한다.
그리고 6 번 으로 돌아와서 보면, 4 번 노드는 visited 처리가 되어있으므로 6 번도 stack 에 push 한다.
그리고 나머지는 모두 차례로 push 하면 된다.
이렇게 첫 번째 DFS 가 끝났다. 어려운 과정은 하나도 없었다.
코사리주 알고리즘 - 두 번째 DFS
이번에는 첫 번째 본 그래프를 역방향으로 뒤집는다. 그리고 쌓은 stack 을 후입선출에 따라 역순으로 pop 해나가면서 탐색한다.
역방향으로 돌린 그래프이다. 이 때, visited 배열은 다시금 처음상태로 초기화 해준다.
첫 번째 DFS 과정에서 스택순회 시, 맨 위에 0 번 노드가 있었으므로 거기부터 그래프 순회가 시작된다. visited 처리는 물론 안되있는 상태이므로, 0 번에서 3 번, 2번, 1번 순으로 진행한다. 이 또한 visited 처리가 안되어있으므로 무사히 돈다.
돌면서, 미리 만들어둔 SCC 이차원 배열에 노드를 넣는다. 아마 SCC[0] 에는 0, 3, 2, 1 로 들어가있을 것이다.
그 후, 1 번 노드에서 0 번 노드로 갈 때, 0 번 노드가 visited 가 되어있으므로 그 때 부터 다시 역으로 돌면서 DFS 를 나온다.
다시 stack 순회로 돌아와서, 0 번 노드 다음에 1 번 노드가 있으므로 거기서 부터 시작한다.
그림으로 보면 다음과 같다. 그래프 순회에서 다시 stack 순회로 돌아왔다.
현 상황은 stack 에서 0 번 노드만 빠지고 나머지는 다 존재하는 상황이다. 다음 노드들인 1 번, 2 번은 이미 visited 처리가 되어있으므로 바로 pop 하고 넘긴다.
그리고 4 번 노드가 visited 처리가 되어있지 않으므로 다시 stack 순회에서 그래프 순회로 돌아가서 4 번 노드부터 시작한다.
그러면 아래와 같은 SCC 가 생기고 SCC[1] 에는 4, 6, 5 순으로 들어가게 될 것이다.
다시 stack 순회로 돌아와서 visited 인 5 번 6 번은 바로 pop 시키고 7 번 노드로 가게되는데, 여기는 그냥 노드 혼자서 SCC가 되므로 SCC[2] 에는 7 하나만이 들어가있을 것이다.
그리고 마지막 stack 요소인 3 까지 visited 처리됨으로 인해 pop 시키면, 아래와 같은 SCC 3개가 나온다.
이것이 SCC 개수와 요소들을 찾는 과정이었다. 이것을 연습할 수 있는 백준 문제가 있었다.
stack 말고 재귀 DFS 로도 풀어보자. (추가적인 순회순서를 적어놓을 배열공간이 필요함)