[알고리즘] 코사라주 알고리즘

코라사주 알고리즘은 SCC(Strongly Connected Component) 문제를 해결하기 위한 알고리즘입니다. SCC란 강한 연결 관계라고 번역될 수 있습니다.

 

1. 강한 연결 관계?

 

SCC는 그래프에서 노드 간의 연결 관계가 주어질 때, 정점들의 최대 부분 집합으로, 부분 집합에 들어있는 서로 다른 노드 u와 노드 v에 대하여, u에서 v로 가는 경로와 v에서 u로 가는 경로가 모두 존재하는 경우를 뜻합니다.

 

강한 연결 관계

 

위의 그래프에서 1, 2, 3번 노드는 각각 서로의 노드로 갈 수 있는 노드가 모두 존재합니다. 예를 들어, 1번 노드에서 3번 노드로 가는 경로가 존재하고, 3번 노드에서 1번 노드로 가는 경로도 존재하죠. 하지만 4번과 5번의 경우, 1, 2, 3번 노드로부터 갈 수는 있으나 4 또는 5번 노드에서 1, 2, 3번 노드로 향하는 경로는 존재하지 않습니다.

 

이런 경우 1, 2, 3번 노드를 하나의 강한 연결 관계(SCC)라고 부릅니다.

 

2. 코사라주 알고리즘

 

위에서 알아본 강한 연결 관계, 즉 SCC에 속하는 노드들을 구하는 알고리즘 중 하나가 바로 코사라주 알고리즘입니다. 일반적으로 이 SCC 문제를 해결하기 위하여 코사라주 알고리즘과 타잔 알고리즘 중 하나를 택하여 사용합니다.

 

이 두 알고리즘 모두 DFS를 기반으로 구현합니다. 각각 타잔 알고리즘은 적용이 쉽고, 코사라주 알고리즘은 구현이 쉬운 장점을 가지고 있으며, 오늘은 코사라주 알고리즘에 대해서만 살펴보도록 하겠습니다.

 

 

코사라주 알고리즘을 구현하기 위해서는 다음의 3가지 준비물이 필요합니다.

 

1. 순방향 그래프

2. 역방향 그래프

3. 스택

 

순방향 그래프(좌측)와 역방향 그래프(우측)

 

순방향 그래프는 우리가 문제에서 입력을 받는 그래프를 말합니다. 그리고 이 그래프의 모든 간선의 방향을 반대 방향으로 향하게 바꾼(1에서 2로 향하는 간선을 2에서 1로 향하는 간선으로 바꾼) 그래프를 역방향 그래프라고 합니다. 마지막으로 노드의 번호를 넣을 수 있는 스택을 준비해줍니다.

 

알고리즘은 다음과 같이 진행됩니다.

 

1. 아직 방문하지 않은 모든 정점에 대하여 순방향 그래프를 이용하여 DFS를 수행해준다. 이 과정에서 탐색이 끝난 노드부터 스택에 PUSH 해준다.

(위 그림의 그래프를 예시로 하면 스택에는 3-2-4-5-1 순서로(top이 1) 담기게 됩니다.)

 

2. 스택으로부터 스택이 완전히 빌 때까지 하나씩 POP 하면서 방문하지 않은 정점에 대하여 역방향 그래프를 이용하여 DFS를 수행해준다. 이 과정에서 탐색되는 모든 노드는 하나의 SCC에 포함된다. 

 

신기하게도 위의 간단한 알고리즘만을 통해서도 SCC를 쉽게 알아낼 수 있습니다. 코드를 보면 더 자세한 작동을 알 수 있을 것같아 코드를 작성해두었습니다.

 

아래는 SCC를 구하는 JAVA 코드입니다. (백준 온라인 저지의 [2150번: Strongly Connected Component]에 대한 정답 소스입니다.)

 

https://www.acmicpc.net/problem/2150

2150번: Strongly Connected Component

 

import java.io.*;
import java.util.*;
 
public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    static ArrayList<ArrayList<Integer>> conn = new ArrayList<>(); // 순방향 그래프
    static ArrayList<ArrayList<Integer>> reconn = new ArrayList<>(); // 역방향 그래프
    static boolean[] visit; // 방문 여부 확인
    static int[] scc; // 어떤 노드들이 하나의 SCC로 묶였는지를 표시하기 위한 배열
    static Stack<Integer> stack = new Stack<>(); // 스택
 
    static int N, M;
 
    public static void dfs(int node) { // 순방향 그래프에 대한 dfs
        visit[node] = true; // 방문했다고 체크
 
        for (int i = 0; i < conn.get(node).size(); i++) {
            int next = conn.get(node).get(i); // 다음 탐색할 노드 선정
 
            if (visit[next] == false) { // 아직 방문하지 않은 노드라면
                dfs(next); // 순방향 그래프에 대한 dfs 진행
            }
        }
        stack.push(node); // 탐색이 끝난 노드는 스택에 push
    }
 
    public static void redfs(int node, int number) { // 역방향 그래프에 대한 dfs.
                                                     // node: 현재 탐색 중인 node, number: 현재 scc 번호
        visit[node] = true; // 방문했다고 체크
        scc[node] = number; // 탐색되는 노드는 현재 scc에 포함
 
        for (int i = 0; i < reconn.get(node).size(); i++) {
            int next = reconn.get(node).get(i); // 다음 탐색할 노드 선정
            if (visit[next] == false) { // 아직 방문하지 않은 노드라면
                redfs(next, number); // 역방향 그래프에 대한 dfs 진행
            }
        }
    }
 
    public static void main(String[] args) throws IOException {
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        visit = new boolean[N + 1];
        scc = new int[N + 1];
 
        for (int i = 0; i < N + 1; i++) {
            conn.add(new ArrayList<>());
            reconn.add(new ArrayList<>());
        }
 
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
 
            int n = Integer.parseInt(st.nextToken());
            int m = Integer.parseInt(st.nextToken());
 
            conn.get(n).add(m);
            reconn.get(m).add(n);
        }
 
        for (int i = 1; i < N + 1; i++) { // 모든 정점에 대하여
            if (visit[i] == false) { // 방문한 노드를 제외하고
                dfs(i); // 순방향 그래프에 대한 dfs 실행
            }
        }
 
        Arrays.fill(visit, false); // 방문 여부를 체크할 visit 배열 초기화
 
        int num = 1;
        while (!stack.isEmpty()) { // 스택이 빌 때 까지
            int node = stack.pop();
 
            if (visit[node] == false) { // 이미 방문한 노드가 아니면
                redfs(node, num++); // 역방향 그래프에 대한 dfs 실행
            }
        }
 
        /*
        여기까지 진행하면 scc 배열로부터 어떤 노드들끼리 하나의 scc를 형성하는지를 알 수 있습니다.
        아래의 코드는 백준 온라인 저지 [2150번: Strongly Connected Component]의 출력 형식을 맞추기 위한 코드입니다.
         */
 
        HashSet<Integer> hs = new HashSet<>(); // HashSet을 이용하여 몇 개의 scc가 존재하는지 파악
        for (int i = 1; i <= N; i++) {
            hs.add(scc[i]);
        }
        bw.write(String.valueOf(hs.size()) + "\n"); // scc의 갯수 출력
 
        Arrays.fill(visit, false);
        for (int i = 1; i <= N; i++) { // 각각의 scc에 속하는 노드들을 출력
            
            if (visit[i] == false) {
                int tmp = scc[i];
                visit[i] = true;
                bw.write(String.valueOf(i) + " ");
                for (int j = 1; j <= N; j++) {
                    if (i == j)
                        continue;
 
                    if (tmp == scc[j]) {
                        bw.write(String.valueOf(j) + " ");
                        visit[j] = true;
                    }
                }
                bw.write("-1\n");
            }
        }
 
        bw.flush();
        bw.close();
        br.close();
    }
}