[USACO Gold] DAG - 위상 정렬

위상 정렬이란, Directed Acyclic Graph(DAG)의 정점들을 각 정점이 자신의 자식 정점들보다 먼저 방문되도록 나열하는 것을 의미한다.

• 방향 그래프(directed graph)는 간선을 한쪽 방향으로만 이동할 수 있는 그래프를 의미한다.
• 또한 비순환 그래프(acyclic graph)는 순환(cycle)을 포함하지 않는 그래프를 의미한다.
  • 이는 하나 이상의 간선을 따라가서 출발한 정점으로 다시 돌아올 수 없는 구조를 말한다.
• 이 두 정의를 합치면, 방향 비순환 그래프(directed acyclic graph, 줄여서 DAG)는 간선을 한쪽 방향으로만 이동할 수 있고 순환을 포함하지 않는 그래프이다.

---

위상 정렬 (Topological Sort) - Course Schedule

다음 문제를 풀어보자.

CSES - Course Schedule

 

 

방향 비순환 그래프에서 위상 정렬이란, 정점들을 일렬로 나열하는 방법으로서, 모든 간선 u -> v에 대해 u가 v보다 먼저 오도록 정점을 배치하는 것을 말한다.

 

위상 정렬을 구현하는 대표적인 방법은 두 가지가 있으며, 하나는 DFS를 이용하는 방식이고 다른 하나는 BFS를 이용하는 방식입니다.

마음에 드는 방식으로 구현하면 된다.
하지만 여기서 보지 않더라도 이번 장에선 둘 다 살펴보게 된다.

DFS 풀이

import java.io.*;
import java.util.*;

public class CourseSchedule {
    private static List<Integer>[] graph;
    private static List<Integer> topSort = new ArrayList<>();
    private static boolean[] visited;

    public static void main(String[] args) throws IOException {
        BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(read.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());

        graph = new ArrayList[n];
        for (int i = 0; i < n; i++) { graph[i] = new ArrayList<>(); }
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(read.readLine());
            int a = Integer.parseInt(st.nextToken()) - 1;
            int b = Integer.parseInt(st.nextToken()) - 1;
            graph[a].add(b);
        }

        visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                visited[i] = true;
                dfs(i);
            }
        }
        Collections.reverse(topSort);

        int[] ind = new int[n];
        for (int i = 0; i < n; i++) { ind[topSort.get(i)] = i; }

        boolean valid = true;
    checkSort:
        for (int i = 0; i < n; i++) {
            for (int j : graph[i]) {
                if (ind[j] <= ind[i]) {
                    valid = false;
                    break checkSort;
                }
            }
        }

        if (!valid) {
            System.out.println("IMPOSSIBLE");
        } else {
            StringBuilder ans = new StringBuilder();
            topSort.forEach(node -> ans.append(node + 1).append(' '));
            ans.setLength(ans.length() - 1);
            System.out.println(ans);
        }
    }

    private static void dfs(int node) {
        for (int next : graph[node]) {
            if (!visited[next]) {
                visited[next] = true;
                dfs(next);
            }
        }
        topSort.add(node);
    }
}

BFS 풀이

import java.io.*;  
import java.util.ArrayDeque;  
import java.util.ArrayList;  
import java.util.Deque;  
import java.util.List;  

public class Main{  
    public static void main(String[] args) throws IOException {  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        PrintWriter pw = new PrintWriter(new BufferedWriter(new OutputStreamWriter(System.out)));  
        int n = 0, m = 0;  
        String s = br.readLine();  
        String[] split = s.split(" ");  
        n = Integer.parseInt(split[0]);  
        m = Integer.parseInt(split[1]);  

        List<Integer>[] graph = new ArrayList[n];  
        for(int i = 0; i<n; i++){  
            graph[i] = new ArrayList<>();  
        }  

        for(int i = 0; i<m; i++){  
            s = br.readLine();  
            split = s.split(" ");  
            int a = Integer.parseInt(split[0]);  
            int b = Integer.parseInt(split[1]);  
            graph[--a].add(--b);  
        }  
        CourseSchedule courseSchedule = new CourseSchedule(n, graph);  
        List<Integer> courseOrder = courseSchedule.getCourseOrder();  
        if(courseOrder.size() != n){  
            pw.println("IMPOSSIBLE");  
            pw.flush();  
            pw.close();  
            br.close();  
            return;  
        }  
        courseOrder.forEach(it -> pw.print(++it + " "));  
        pw.println();  
        pw.flush();  
        pw.close();  
        br.close();  
    }  
}  
class CourseSchedule {  
    private final List<Integer>[] graph;  
    private final Deque<Integer> deque = new ArrayDeque<>();  
    private final int[] indegree;  
    private int n;  
    public CourseSchedule(int n, List<Integer>[] graph) {  
        this.graph = graph;  
        this.n = n;  
        this.indegree = new int[n];  
        for(int i = 0; i<n; i++){  
            for(int next : graph[i]){  
                indegree[next]++;  
            }  
        }  
        for (int i = 0; i < n; i++) {  
            if(indegree[i] == 0){  
                deque.add(i);  
            }  
        }  
    }  
    public List<Integer> getCourseOrder(){  
        List<Integer> ret = new ArrayList<>();  
        while(!deque.isEmpty()){  
            int now = deque.poll();  
            ret.add(now);  
            for(int next : graph[now]){  
                indegree[next]--;  
                if(indegree[next] == 0){  
                    deque.add(next);  
                }  
            }  
        }  
        return ret;  
    }  
}

---

사이클 찾기

다음 문제를 풀어보자.

CSES - Round Trip II

 

 

위상 정렬이 존재하지 않는 경우, 위에서 설명한 DFS 알고리즘을 변형하여 방향 그래프에서 사이클을 찾아낼 수 있다.

 

사이클을 찾는 방법은, 탐색 과정에서 방문하는 각 노드를 스택에 넣어두다가 이미 스택에 존재하는 노드를 다시 방문했을 때 사이클을 검출하는 방식이다.

 

예를 들어, 현재 스택이 s1,s2,…,si​로 구성되어 있고, 이후 방문한 노드가 u=sj (j≤i)라면,
사이클은 다음과 같이 표현된다.

그리고, 잡기술로 스택을 명시적으로 전부 저장하지 않고도 사이클을 복원할 수 있다.

• 노드 u를 "스택에 속하지 않는다"고 표시한 뒤
• DFS 백트래킹을 통해 다시 u에 도달할 때까지 거슬러 올라가면 된다.

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.ArrayList;  
import java.util.Collections;  
import java.util.List;  
import java.util.StringTokenizer;  

public class Main {  
    public static void main(String[] args) throws IOException {  
        int n, m;  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringTokenizer stringTokenizer = new StringTokenizer(br.readLine());  
        n = Integer.parseInt(stringTokenizer.nextToken());  
        m = Integer.parseInt(stringTokenizer.nextToken());  
        List<Integer>[] graph = new ArrayList[n];  
        for(int i = 0; i<n; i++) {  
            graph[i] = new ArrayList<>();  
        }  
        for(int i = 0; i<m; i++) {  
            stringTokenizer = new StringTokenizer(br.readLine());  
            int a = Integer.parseInt(stringTokenizer.nextToken()) - 1;  
            int b = Integer.parseInt(stringTokenizer.nextToken()) - 1;  
            graph[a].add(b);  
        }  
        RoundTrip roundTrip = new RoundTrip(n, graph);  
        List<Integer> cycle = roundTrip.getCycle();  
        if(cycle.isEmpty()) {  
            System.out.println("IMPOSSIBLE");  
            return;  
        }  
        System.out.println(cycle.size() + 1);  
        cycle.forEach(it -> System.out.print((it + 1) + " "));  
        System.out.println(cycle.get(0) + 1);  
    }  
}  

class RoundTrip {  
    private final int n;  
    private final List<Integer>[] graph;  
    private final boolean[] visited;  
    private final boolean[] onStack;  
    private final List<Integer> cycle = new ArrayList<>();  

    public RoundTrip(int n, List<Integer>[] graph) {  
        this.n = n;  
        this.graph = graph;  
        this.visited = new boolean[n];  
        this.onStack = new boolean[n];  
    }  
    public List<Integer> getCycle() {  
        for(int i = 0; i<n; i++){  
            if(!visited[i]){  
                dfs(i);  
            }  
            if(!cycle.isEmpty()){  
                break;  
            }  
        }  
        Collections.reverse(cycle);  
        return cycle;  
    }  

    private boolean dfs(int v) {  
        visited[v] = true;  
        onStack[v] = true;  
        for (int next : graph[v]) {  
            if (onStack[next]) {  
                onStack[next] = false;  
                onStack[v] = false;  
                cycle.add(v);  
                return true;  
            } else if (!visited[next]) {  
                if (dfs(next)) {  
                    if (onStack[v]) {  
                        cycle.add(v);  
                        onStack[v] = false;  
                        return true;  
                    } else {  
                        cycle.add(v);  
                        return false;  
                    }  
                }  
                if(!cycle.isEmpty()){  
                    return false; // 사이클을 찾았으므로, 탐색을 중단함.  
                }  
            }  
        }  
        onStack[v] = false;  
        return false;  
    }  
}

---

동적 계획법 (Dynamic Programming)

참고 자료: CPH16.2 - Dynamic Programming

 

이름에서 알 수 있듯이, 방향 비순환 그래프(DAG)의 유용한 성질 중 하나는 사이클이 없다는 것이다.
그래프의 각 정점을 하나의 상태(state)로 보면, 모든 간선 u→v에 대해 u가 v보다 먼저 처리되도록 상태들을 순서대로 처리하면 그래프 위에서 동적 계획법을 수행할 수 있다.

다행히도, 이것이 바로 위상 정렬의 정확한 정의다!

예제 - Longest Flight Route

다음 문제를 풀어보자.

CSES - Longest Flight Route

 

 

이 문제에서 우리는 DAG에서 가장 긴 경로를 찾아야 한다.

풀이 - Longest Flight Route

dp[v]를 정점 v에서 끝나는 가장 긴 경로의 길이로 정의하자.

그러면 자명하게 다음과 같이 점화식을 세울 수 있다.

또는 v가 정점 1이라면 1이다.

 

상태들을 위상 순서로 처리하면, dp[v]를 계산할 때 이미 모든 dp[u]가 계산되어 있음이 보장된다.

import java.io.BufferedReader;  
import java.io.IOException;  
import java.io.InputStreamReader;  
import java.util.*;  

public class Main {  
    public static void main(String[] args) throws IOException {  
        int n, m;  
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));  
        StringTokenizer st = new StringTokenizer(br.readLine());  
        n = Integer.parseInt(st.nextToken());  
        m = Integer.parseInt(st.nextToken());  
        List<Integer>[] graph = new ArrayList[n];  
        for (int i = 0; i < n; i++) {  
            graph[i] = new ArrayList<>();  
        }  

        for (int i = 0; i < m; i++) {  
            st = new StringTokenizer(br.readLine());  
            int a = Integer.parseInt(st.nextToken()) - 1;  
            int b = Integer.parseInt(st.nextToken()) - 1;  
            graph[a].add(b);  
        }  
        LongestFlightRoute longestFlightRoute = new LongestFlightRoute(graph, n);  
        List<Integer> longestFlightPath = longestFlightRoute.getLongestFlightRoute(0, n - 1);  
        if (longestFlightPath.isEmpty()) {  
            System.out.println("IMPOSSIBLE");  
            return;  
        }  
        System.out.println(longestFlightPath.size());  
        longestFlightPath.forEach(it -> System.out.print((it + 1) + " "));  
        System.out.println();  
    }  
}  

class LongestFlightRoute{  
    private final List<Integer>[] graph;  
    private final int n;  
    private final int[] dp;  
    private final int[] indegree;  
    private final int[] before;  

    public LongestFlightRoute(List<Integer>[] graph, int n) {  
        this.graph = graph;  
        this.n = n;  
        this.dp = new int[n];  
        this.before = new int[n];  
        Arrays.fill(before, -1);  
        this.indegree = new int[n];  

        Queue<Integer> queue = new ArrayDeque<>();  
        boolean[] visited = new boolean[n];  
        queue.add(0);  
        visited[0] = true;  
        while (!queue.isEmpty()) {  
            int now = queue.poll();  
            for (int next : graph[now]) {  
                indegree[next]++;  
                if (!visited[next]) {  
                    visited[next] = true;  
                    queue.add(next);  
                }  
            }  
        }  
    }  

    public List<Integer> getLongestFlightRoute(int start, int end){  
        Deque<Integer> queue = new ArrayDeque<>();  
        queue.offer(start);  

        while(!queue.isEmpty()){  
            int now = queue.poll();  
            dp[now]++;  
            for(int next : graph[now]){  
                indegree[next]--;  
                if(dp[next] < dp[now]){  
                    dp[next] = dp[now];  
                    before[next] = now;  
                }  
                if(indegree[next]==0){  
                    queue.offer(next);  
                }  
            }  
        }  
        List<Integer> path = new ArrayList<>();  
        if(dp[end] == 0) return path;  

        while(end != start){  
            path.add(end);  
            end = before[end];  
        }  
        path.add(start);  
        Collections.reverse(path);  
        return path;  
    }  
}

---

추천 문제

• https://cses.fi/problemset/task/1681
• https://www.acmicpc.net/problem/15758