백준 2252 (줄 세우기) - java

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

2252번: 줄 세우기

유형 : 위상정렬

위상 정렬

• 조건 : DAG (사이클이 없는 방향 그래프)
• 순서
  1. 진입차수가 0인 방문하지 않은 정점을 큐에 삽입한다.
  2. 큐에서 원소를 꺼내 연결된 모든 간선을 제거한다.
  3. 간선 제거 이후에 진입차수가 0이 된 정점을 큐에 삽입한다.
  4. 큐가 빌때까지 2~3번 과정을 반복한다.
  5. 만약 모든 원소를 방문하기 전에 큐가 빈다면 사이클이 존재하는 것 이고, 모든 원소를 방문했다면 큐에서 꺼낸 순서가 위상 정렬의 결과이다.

전체 코드

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

public class Main {
    static int n = 0;
    static int m = 0;
    static int[] count;
    static boolean[] visit;
    static ArrayList<Integer>[] graph;
    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());
        m = Integer.parseInt(st.nextToken());
        count = new int[n+1];
        visit = new boolean[n+1];
        graph = new ArrayList[n+1];
        for(int i=1;i<=n;i++){
            graph[i] = new ArrayList<>();
        }

        for(int i=1;i<=m;i++){
            st = new StringTokenizer(br.readLine(), " ");
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            graph[x].add(y);
            count[y] += 1;
        }

        Queue<Integer> q = new LinkedList<>();

        for(int i=1;i<=n;i++){
            if(count[i] == 0) {
                q.add(i);
                visit[i] = true;
            }
        }
        StringBuilder sb = new StringBuilder();
        while(!q.isEmpty()){

            int cur = q.poll();
            sb.append(cur+" ");

            for(int next : graph[cur]){
                count[next] -= 1;

                if(count[next] == 0 && !visit[next]){
                    visit[next] = true;
                    q.add(next);
                }
            }

        }
        System.out.println(sb);
        br.close();
    }
    
}