BOJ (Java) 2252번: 줄 세우기

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

---

풀이

순서가 정해져 있는 작업을 수행해야 하므로 위상정렬을 사용했다.

학생들의 키 순서를 저장하여 앞선 사람이 없는 학생부터 차례로 탐색하며 줄을 세웠다.

---

Java 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

public class Main {
    private static int N, M;
    private static List<Integer> orders[];
    private static int[] cnt;
    private static boolean[] visited;
    public static void main(String[] args) throws IOException {
        // input
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        String[] NM = bf.readLine().split(" ");
        N = Integer.parseInt(NM[0]);
        M = Integer.parseInt(NM[1]);

        visited = new boolean[N + 1];
        cnt = new int[N + 1];
        orders = new List[N + 1];
        for (int i = 1; i <= N; i++) {
            orders[i] = new ArrayList<>();
        }

        // 키 순서 저장
        for (int i = 0; i < M; i++) {
            String[] AB = bf.readLine().split(" ");
            int A = Integer.parseInt(AB[0]);
            int B = Integer.parseInt(AB[1]);

            orders[A].add(B);
            orders[B].add(A);
            cnt[B]++;
        }

        printLine();
    }

    private static void printLine() {
        
        // 연결된 숫자가 없는 학생을 큐에 저장
        Queue<Integer> q = new LinkedList<>();
        for (int i = 1; i <= N; i++) {
            if (cnt[i] == 0) {
                q.add(i);
            }
        }

        while (!q.isEmpty()) {
            int now = q.poll();
            visited[now] = true;
            System.out.print(now + " ");

            // 현재 학생과 연결된 학생들의 연결 수를 감소  
            for (int connects : orders[now]) {
                if (!visited[connects]) {
                    cnt[connects]--;
                    
                    // 다음 학생이 연결된 수가 없다면 큐에 저장
                    if (cnt[connects] == 0) {
                        q.add(connects);
                    }
                }
            }
        }

        // 아무와도 연결되지 않은 학생을 출력
        for (int i = 1; i <= N; i++) {
            if (!visited[i]) {
                System.out.print(i + " ");
            }
        }
    }
}