yg log --graph --oneline --all

Home Stack Notes AboutRSS

11. 방향이 생기면 방문 표시만으로는 부족하다

작성 · 5분 읽기 · 조회수 —수정

기초 개념과 예제를 보강하고 시리즈 흐름을 연결

화살표가 있는 연결에서 답을 구분한다

방향 그래프의 간선 u→v는 u에서 v로 갈 수 있다는 뜻이다. 반대 방향 v→u는 별도 간선이다. 수강 순서를 예로 들면 기초→심화는 기초를 먼저 끝내야 심화를 들을 수 있다는 선행 관계로 읽을 수 있다.

작은 입력 하나에도 서로 다른 문제가 들어 있다.

간선: 0→1, 0→2, 1→3, 2→3
도달 가능성: 0에서 3으로 갈 수 있는가       → 가능
순환: 출발점으로 되돌아오는 방향 경로가 있는가 → 없음
위상 순서: 모든 화살표의 앞을 먼저 놓을 수 있는가 → 0,1,2,3

도달 가능성은 u에서 간선을 따라 v에 갈 수 있는지를 묻는다. 사이클(cycle)은 출발 정점으로 돌아오는 닫힌 경로다. 방향 그래프에서 서로 어느 쪽으로도 도달 가능한 정점의 최대 묶음을 강연결요소(SCC)라고 한다. 위상 순서는 모든 간선 u→v에서 u가 v보다 앞에 오는 정점 나열이다. 사이클이 없는 방향 그래프인 DAG에서만 모든 정점을 포함한 위상 순서를 만들 수 있다.

진입 차수는 한 정점으로 들어오는 간선 수다. 위 예시에서 정점 3의 진입 차수는 2다. Kahn 위상 정렬은 진입 차수가 0인, 즉 아직 남은 선행 조건이 없는 정점부터 처리한다.

설명을 끝내지 못한 자리

방향그래프 노트의 마지막은 매끄럽지 않다. Floyd-Warshall 설명을 시작하다가 “위 알고리즘은”에서 문장이 끊겼고, 맨 끝에는 “의사코드 달달 외워라”라고 적어 놓았다. 개념을 이해하고 구현까지 마쳤다고 볼 수 있는 기록은 아니다.

앞부분에는 도달 가능성, 강연결성, 강연결요소, 이행적 폐쇄가 차례로 정리되어 있다. 이번에는 그 목록을 모두 암기하는 대신, 각 개념이 방문 기록에 무엇을 더 물어보는지 나누어 보려 한다. 아래 코드는 당시 저장소의 제출 코드가 아니라 이 구분을 확인하려고 새로 작성한 것이다.

한 방향으로 닿는 것과 돌아오는 것은 다르다

0→1→2에서는 0에서 DFS를 시작하면 셋을 모두 방문한다. 그렇다고 셋이 강연결인 것은 아니다. 2에서 출발하면 0으로 돌아갈 수 없다. “0이 모두에게 도달한다”와 “모든 정점이 서로에게 도달한다”는 다른 조건이다.

노트에는 그래프 전체의 강연결성을 확인하는 절차가 적혀 있다. 임의의 정점 s에서 원래 그래프를 순회하고, 간선을 모두 뒤집은 그래프에서도 s에서 순회한다. 첫 번째는 s→모두, 두 번째는 원래 방향으로 모두→s가 가능한지 확인한다. 둘 다 참이면 임의의 u에서 u→s→v로 갈 수 있다.

이 검사는 전체가 한 덩어리인지 답한다. 거짓일 때 강연결요소가 몇 개이고 어디서 나뉘는지까지 알려주지는 않는다. 예를 들어 0↔1, 1→2, 2↔3에서는 {0,1}과 {2,3} 두 강연결요소가 있지만, 두 집합 사이에는 돌아오는 길이 없다.

이미 방문한 정점이 보여도 순환은 아닐 수 있다

이번에 먼저 구현한 것은 순환 검사다. 다음 방향 그래프를 번호순으로 DFS한다고 하자.

0 -> 1 -> 3
0 -> 2 -> 3

0→1→3을 처리한 뒤 0으로 돌아와 2를 방문하면 이미 방문한 3을 다시 만난다. 하지만 이 그래프에는 순환이 없다. 3의 탐색이 끝난 상태이기 때문이다.

반대로 0→1→2를 탐색하던 중 2→0을 만나면, 0은 아직 재귀 호출 스택에 남아 있다. 현재 경로를 따라 0에서 2로 왔고 다시 0으로 갈 수 있으므로 순환이 생긴다. 불리언 방문 표시를 세 가지 상태로 나눌 이유다.

색 뜻 이 정점으로 가는 간선을 만났을 때
0 아직 시작하지 않음 재귀로 들어간다
1 탐색 중, 현재 호출 경로에 있음 방향 순환을 발견했다
2 이웃까지 모두 처리함 이것만으로 순환이라고 할 수 없다 
static bool cycle_visit(const Graph *g, int u, int color[N]) {
    color[u] = 1; /* active call */
    for (Node *p = g->adj[u]; p; p = p->next) {
        int v = p->vertex;
        if (color[v] == 1) return true;
        if (color[v] == 0 && cycle_visit(g, v, color)) return true;
    }
    color[u] = 2; /* completed call */
    return false;
}

이 규칙은 방향 그래프용이다. 무방향 그래프는 부모로 돌아가는 간선도 양쪽에 저장되므로 그대로 적용하면 트리조차 순환이라고 판단한다. 어떤 종류의 그래프인지가 방문 표시의 해석을 결정한다.

선행 조건이 모두 끝난 정점부터 처리한다

방향을 “먼저 해야 할 일→나중에 해야 할 일”로 읽으면 위상 정렬로 이어진다. 여기서는 큐를 쓰는 Kahn 방식으로 보완했다. 들어오는 간선 수가 0인 정점을 먼저 꺼내고, 그 정점에서 나가는 간선을 제거한 효과를 반영한다.

for (Node *p = g->adj[u]; p; p = p->next) {
    if (--degree[p->vertex] == 0) {
        queue[tail++] = p->vertex;
    }
}

앞의 그래프에서는 처음 0만 처리할 수 있다. 0을 처리하면 1과 2가 준비된다. 1을 처리한 뒤에도 3의 진입 차수는 1이라 기다린다. 2까지 끝나야 3이 큐에 들어간다. 결과 0 1 2 3에서 모든 간선은 앞에서 뒤로 향한다.

큐가 비었는데 처리한 정점 수가 V보다 작으면 방향 순환이 있다. 다만 남아 있는 정점 전부가 순환 위에 있다는 뜻은 아니다. 순환에서 나오는 간선을 기다리는 뒤쪽 정점도 함께 남을 수 있다. 방향 그래프에 위상 순서가 존재하는 조건은 DAG, 즉 방향 순환이 없다는 것이다. Algorithms, 4th Edition의 방향 그래프와 위상 정렬

강연결요소는 끝난 순서를 이용한다

이번 검증 코드의 scc는 Kosaraju 방식으로 각 정점에 그룹 번호를 붙인다. 원래 그래프의 DFS가 끝나는 순서를 모은 뒤, 그 역순으로 정점을 꺼내 뒤집은 그래프를 순회한다. 두 그래프의 역할을 반대로 바꾸어 구성할 수도 있다.

출발 정점을 단순히 번호순으로 고르는 것과 다른 이유는 강연결요소 사이의 방향 때문이다. 한 요소에서 다른 요소로 갈 수 있어도 돌아오는 길이 없을 수 있다. 종료 순서를 이용하면 두 번째 순회가 아직 분류하지 않은 다른 요소까지 무작정 합쳐 버리는 일을 막는다. 같은 요소 내부에서는 방향을 뒤집어도 서로 도달 가능하므로 함께 묶인다.

이 글의 중심은 세 가지 질문의 구분이다. 순환 검사는 현재 재귀 경로로 돌아오는지, 위상 정렬은 선행 관계를 만족하는 순서가 있는지, 강연결요소는 서로 왕복 가능한 최대 묶음이 무엇인지 묻는다. DFS를 쓴다는 공통점만으로 같은 방문 배열 하나에 모두 맡길 수는 없다.

새 코드에서는 인접리스트를 뒤집는 데 O(V+E), 각 순회에도 O(V+E)가 걸리도록 구성했다. 정점 4개의 자기 루프 없는 방향 그래프 4,096개를 전부 만들어, SCC의 그룹 일치 여부를 행렬로 구한 양방향 도달 가능성과 비교했다. 순환 검사의 결과와 위상 정렬의 성공 여부도 서로 맞는지 검사했다.

노트에서 끊긴 Floyd-Warshall은 전체 정점 쌍의 도달 가능성을 다루는 다른 길이다. 이번에는 검증의 기준으로 사용했으며, 그 점화식의 전개까지 이 글에서 마친 것은 아니다. 남겨 둔 개념을 한꺼번에 “이해 완료”로 덮기보다, 각 질문을 코드와 예제로 구분하는 데서 다시 시작한다.

기록과 실행 코드

관련 포스트