[GDG - 스터디] 위상정렬을 이용한 줄 세우기

위상정렬 알고리즘

위상정렬(Topology Sort) ?

• 위상정렬 알고리즘은 사이클이 없는 그래프에서 노드의 순서를 찾는 정렬 알고리즘이다.
• 그래프 내의 노드들 간의 선후 관계를 결정하여, 어떤 작업들이 먼저 수행되어야 하는지 순서를 정하는 것이 목표이다. → 작업의 선후 관계를 결정해야 하거나 특정 순서로 작업을 처리해야 하는 문제에서 사용된다 !

---

💡 위상정렬 핵심 개념 - 유향 비순환 그래프(DAG)

• 위상정렬은 반드시 사이클이 없는 유향 그래프에서만 적용 가능하다 ! → 그 이유는 당연하게도 사이클이 있다면, 노드 간의 선행 관계를 정의할 수 없기 떄문에 !

<aside> 💡

선행 관계 ?

• 간선(u → v)이 있을 때, u는 항상 v보다 앞에 와야 한다는 의미이다. </aside>

---

💡 위상정렬 핵심 개념 - 진입 차수(In-degree)

• 진입 차수는 특정 노드로 들어오는 간선의 개수를 의미한다.
• 진입 차수가 0인 노드는 현재 해당 노드 이전에 처리해야 할 노드가 없다는 것을 의미 ! ****→ 위상정렬 과정에서 진입 차수가 0인 노드를 처리하며 간선을 제거한다.

---

💡 위상정렬 핵심 개념 - 정렬 순서

• 위상정렬의 결과는 그래프의 노드들이 선행 관계를 만족하는 일종의 선형 순서를 의미한다.
• 위상정렬은 항상 하나의 고유한 순서를 가지지는 않을 수 있으며, 경우에 따라 여러 가지 결과가 나올 수 있다.

---

💡 위상정렬 - 구현

Kahn's Algorithm(진입 차수 기반)

• 이 방법에선 다음 두 가지 내용이 핵심 로직이다.
  • 진입 차수가 0인 노드를 큐에 넣고, 해당 노드를 처리하면서 간선을 제거한다.
  • 간선을 제거한 후 진입 차수가 0이 되는 노드를 다시 큐에 추가한다.
• 시간 복잡도: O(V + E) (노드 수 V, 간선 수 E)
• 구현 단계
  1. 그래프는 인접 행렬이나 인접 리스트로 구현한다.
  2. 모든 노드의 진입 차수를 계산한다. → inDegree 배열에 계산한 진입 차수들을 저장한다.
  3. 진입 차수가 0인 노드를 큐에 삽입한다.
  4. 큐에서 노드를 꺼내 정렬 결과에 추가하고, 해당 노드와 연결된 간선을 제거한다.
  5. 연결된 간선이 제거된 노드의 진입 차수를 감소시키고, 진입 차수가 0이 되면 큐에 삽입한다.
  6. 큐가 빌 때까지 반복한다.

import java.util.*;

public class TopologicalSort {
    public static void main(String[] args) {
        // 그래프 예제: 인접 리스트 형태로 초기화
        int nodes = 6; // 노드의 개수
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < nodes; i++) {
            graph.add(new ArrayList<>());
        }
        
        // 간선 추가: u → v
        graph.get(5).add(2);
        graph.get(5).add(0);
        graph.get(4).add(0);
        graph.get(4).add(1);
        graph.get(2).add(3);
        graph.get(3).add(1);
        
        // 위상 정렬 수행
        List<Integer> sortedOrder = topologicalSort(nodes, graph);
        
        // 위상 정렬 결과 출력
        if (sortedOrder.size() == nodes) {
            System.out.println("위상 정렬 결과: " + sortedOrder);
        } else {
            System.out.println("그래프에 사이클이 존재합니다. 위상 정렬이 불가능합니다.");
        }
    }
    
    public static List<Integer> topologicalSort(int nodes, List<List<Integer>> graph) {
        List<Integer> sortedOrder = new ArrayList<>(); // 정렬 결과를 저장할 리스트
        int[] inDegree = new int[nodes]; // 각 노드의 진입 차수를 저장하는 배열
        
        // 모든 노드의 진입 차수 계산
        for (int u = 0; u < nodes; u++) {
            for (int v : graph.get(u)) {
                inDegree[v]++;
            }
        }
        
        // 진입 차수가 0인 노드를 큐에 추가
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < nodes; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        // 그래프 처리
        while (!queue.isEmpty()) {
            int node = queue.poll(); // 큐에서 노드 제거
            sortedOrder.add(node); // 정렬 결과에 추가
            
            // 현재 노드와 연결된 간선 제거
            for (int neighbor : graph.get(node)) {
                inDegree[neighbor]--; // 진입 차수를 감소
                if (inDegree[neighbor] == 0) { // 진입 차수가 0이 된 노드를 큐에 추가
                    queue.offer(neighbor);
                }
            }
        }
        
        return sortedOrder; // 위상 정렬 결과 반환
    }
}

---

💡 위상정렬 - 구현

DFS 기반

• DFS 탐색 과정에서 “자식 노드 → 부모 노드" 순서로 처리하는 로직을 이용하여 선행 관계를 만족하는 위상정렬 결과를 얻는 구현 방법이다 ! → 즉, 자식 노드를 모두 방문한 후에 부모 노드를 처리하는 DFS의 성질을 이용한 것 !
• 시간 복잡도: O(V + E) (노드 수 V, 간선 수 E)
• 구현 단계
  1. 인접 리스트를 사용하여 그래프를 표현한다. → graph.get(u).add(v)는 노드 u에서 v로의 간선을 추가하는 것 !
  2. 각 노드에 대해 DFS를 수행한다. → 이미 방문한 노드는 다시 탐색하지 않는다..
  3. DFS에서 모든 자식 노드 탐색이 끝난 후, 현재 노드를 스택에 추가한다. → 스택의 역순으로 노드들을 꺼내면 위상정렬 결과가 됩니다.
  4. 최종적으로 스택에서 모든 노드를 꺼내 리스트에 저장한다.

import java.util.*;

public class TopologicalSortDFS {
    public static void main(String[] args) {
        // 그래프 예제: 인접 리스트 형태로 초기화
        int nodes = 6; // 노드의 개수
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i < nodes; i++) {
            graph.add(new ArrayList<>());
        }

        // 간선 추가: u → v
        graph.get(5).add(2);
        graph.get(5).add(0);
        graph.get(4).add(0);
        graph.get(4).add(1);
        graph.get(2).add(3);
        graph.get(3).add(1);

        // 위상 정렬 수행
        List<Integer> sortedOrder = topologicalSort(nodes, graph);

        // 결과 출력
        System.out.println("위상 정렬 결과: " + sortedOrder);
    }

    public static List<Integer> topologicalSort(int nodes, List<List<Integer>> graph) {
        boolean[] visited = new boolean[nodes]; // 각 노드 방문 여부
        Stack<Integer> stack = new Stack<>();  // 정렬 결과를 저장할 스택

        // 모든 노드를 순회하며 DFS 수행
        for (int i = 0; i < nodes; i++) {
            if (!visited[i]) {
                dfs(i, graph, visited, stack);
            }
        }

        // 스택에서 노드를 꺼내면 위상 정렬 순서가 됨
        List<Integer> sortedOrder = new ArrayList<>();
        while (!stack.isEmpty()) {
            sortedOrder.add(stack.pop());
        }
        return sortedOrder;
    }

    private static void dfs(int node, List<List<Integer>> graph, boolean[] visited, Stack<Integer> stack) {
        visited[node] = true; // 현재 노드를 방문 처리

        // 현재 노드의 모든 인접 노드에 대해 DFS 수행
        for (int neighbor : graph.get(node)) {
            if (!visited[neighbor]) {
                dfs(neighbor, graph, visited, stack);
            }
        }

        // 모든 인접 노드 방문 후 스택에 추가
        stack.push(node);
    }
}

---

문제: 줄 세우기 (백준 2252)

문제 링크

 

---

알고리즘 [접근 방법]

• 키 순으로 줄을 세우는 것이기 때문에 사이클이 없는 방향 그래프가 형성되고, 선후 관계가 존재한다. → 따라서, 진입 차수를 기반으로 구현한 위상 정렬 알고리즘을 사용하여 해결하면 된다.

---

해결 코드

• 이 문제에서 제시한 내용대로 구현하면 아래와 같은 입력값에 대해 3 4 1 2라는 출력값이 나온다. → 위상 정렬은 선행 관계만을 보장하며, 아래처럼 선행 관계를 만족하는 여러 정렬 결과가 존재할 수 있기 때문에, 문제에서 제시한 출력값처럼 나오게 하려면 우선순위 큐를 이용하면 되긴 하다 ! ( 문제에서 “답이 여러 가지인 경우에는 아무거나 출력한다.”라는 조건을 제시했기 떄문에 상관은 없다. )

// 우선순위 큐: 번호가 큰 노드부터 처리
PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());

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

public class Main {
    
    static int N, M;
    static List<List<Integer>> graph;
    static int[] inDegree;
    
    public static void main(String[] args) throws Exception {
        
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        N = Integer.parseInt(st.nextToken());  // 학생 수
        M = Integer.parseInt(st.nextToken());  // 키 비교 횟수
        inDegree = new int[N + 1]; // 각 노드의 진입 차수를 저장하는 배열
        
        graph = new ArrayList<>();
        for (int i = 0; i < N + 1; i++) {
            graph.add(new ArrayList<>());
        }
        
        for (int i = 0; i < M; ++i) {
            st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            graph.get(A).add(B);
        }
        
        List<Integer> sortedOrder = new ArrayList<>();
        sortedOrder = topologicalSort();
        
        StringBuilder sb = new StringBuilder();
        for (int student : sortedOrder) {
            sb.append(student).append(" ");
        }
        
        System.out.print(sb.toString());
    }
    
    public static List<Integer> topologicalSort() {
        List<Integer> sortedOrder = new ArrayList<>(); // 정렬 결과를 저장할 리스트
        
        // 모든 노드의 진입 차수 계산
        for (int u = 1; u <= N; u++) {
            for (int v : graph.get(u)) {
                inDegree[v]++;
            }
        }
        
        // 진입 차수가 0인 노드를 큐에 추가
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i <= N; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }
        
        // 그래프 처리
        while (!queue.isEmpty()) {
            int node = queue.poll(); // 큐에서 노드 제거
            sortedOrder.add(node); // 정렬 결과에 추가
            
            // 현재 노드와 연결된 간선 제거
            for (int neighbor : graph.get(node)) {
                inDegree[neighbor]--; // 진입 차수를 감소
                if (inDegree[neighbor] == 0) { // 진입 차수가 0이 된 노드를 큐에 추가
                    queue.offer(neighbor);
                }
            }
        }
        
        return sortedOrder; // 위상 정렬 결과 반환
    }
}

---

정리

• 위상정렬은 반드시 사이클이 없는 유향 그래프에서 사용하자 !
• 위상 정렬은 선행 관계만을 보장하며, 아래처럼 선행 관계를 만족하는 여러 정렬 결과가 존재할 수 있다는 사실을 알아두자 !

 

https://thin-azimuth-2a9.notion.site/GDG-144f4ee21c0080f48049fa2b3cc838c0?pvs=4

GDG 스터디 - 위상정렬을 이용한 줄 세우기 | Notion