[BOJ] [JAVA] [GOLD 3] 2252: 줄 세우기

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

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

public class BOJ2252 {
    static class Node {
        int vertex;
        Node link;
        public Node (int vertex, Node link) {
            this.vertex = vertex;
            this.link = link;
        }
    }
    static int N, M;
    static Node adjList[];
    static int inDegree[];
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken()); // N명의 학생
        M = Integer.parseInt(st.nextToken()); // 키를 비교한 회수
        adjList = new Node[N+1];
        inDegree = new int[N+1]; // 진입간선의 수 체크를 위한 배열

        for (int m = 0; m < M; m++) {
            st = new StringTokenizer(br.readLine());
            // A가 학생 B의 앞에 서야함
            // A -> B 로 가는 간선
            int A = Integer.parseInt(st.nextToken()); // from, 진출 정점
            int B = Integer.parseInt(st.nextToken()); // to, 진입 정점
            adjList[A] = new Node(B, adjList[A]);
            inDegree[B]++; // 간선을 받는 B++
        }

        ArrayList<Integer> list = topologySort();
        if(list.size() == N) {
            for (Integer vertex : list) {
                System.out.print(vertex + " ");
            }
        } else {
            System.out.println("사이클 발생");
        }
    }

    private static ArrayList<Integer> topologySort() {
        ArrayList<Integer> orderList = new ArrayList<>();
        Queue<Integer> q = new ArrayDeque<>();
        for (int i = 1; i <= N; i++) {
            if(inDegree[i] == 0) q.offer(i); // 진입 차수가 0인 정점 넣기
        }

        while(!q.isEmpty()) {
            int cur = q.poll();
            orderList.add(cur);

            // 현재 정점 기준으로 인접정점 처리
            for (Node temp = adjList[cur]; temp != null; temp = temp.link) {
                if (--inDegree[temp.vertex] == 0) q.offer(temp.vertex);
            }
        }
        return orderList;
    }
}

// tc
/*
3 2
1 3
2 3
answer : 1 2 3

4 2
4 2
3 1
answer : 4 2 3 1 (답은 여러가지)
*/

위상 정렬

• 유향 그래프
• 싸이클 존재하지 않음
• 방향성을 거스리지 않으면서 순서적으로 탐색

• 메커니즘
  • 차수 - 정점에 연결된 간선 수
    • 진출 차수 - 자신의 정점에서 타정점으로 나가는 간선 수
    • 진입 차수 - 타정점에서 자신의 정점으로 들어오는 간선 수
  1. • •  
       1. 진입 차수가 0인 노드(시작점)를 큐에 모두 넣는다.
       2. 큐에서 진입 차수가 0인 노드를 꺼내어 자신과 입전한 노드의 간선을 제거한다.
          1. 인접한 노드의 진입 차수를 1 감소시킨다.
       3. 간선 제거 후 진입 차수가 0이 된 노드를 큐에 넣는다.
       4. 큐가 공백 큐 상태가 될 때 까지 2-3 작업을 반복
          1. 모든 노드가 처리되지 않았다면 사이클 발생
          2. 모든 노드가 다 처리되었다면 위상 정렬 완성