[백준 / 골드3] 2252 줄 세우기 (Java)

어떠한 일을 수행하는데 순서가 존재하고 순서를 위배하지 않게 나열해야 한다면 위상 정렬을 사용하자.

문제 보기

사용한 것

• 한 학생이 다른 한 학생의 앞에 서야한다는 정보들이 주어졌을 때 순서에 위배되지 않고 줄을 세우기 위한 위상정렬

풀이 방법

• 어떤 두 학생이 키를 비교한 결과들을 입력 받고 진입 차수를 기록한다.
• 가장 앞에 세워야 하는 학생들은 진입 차수가 0인 학생들이다. 이 학생들의 앞에 서야할 학생이 존재하지 않기 때문이다.
• 따라서 진입 차수가 0인 학생들 먼저 q에 넣는다.
• q가 비어있을 때 까지 한 학생을 뽑고 result에 넣는다.
• 해당 학생은 순서가 정해졌으니, 해당 학생보다 뒤에 서야되는 모든 학생들의 진입 차수를 1 감소시킨다.
• 만약 진입 차수가 감소한 학생의 진입 차수가 0이 되면 해당 학생도 더 이상 앞에 서있을 학생이 없으니 q에 넣어준다.
• 모든 과정이 완료되면 result를 출력한다.

코드

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String[] line = br.readLine().split(" ");
        int V = Integer.parseInt(line[0]);
        int[] inDegree = new int[V + 1];
        List<List<Integer>> graph = new ArrayList<>();
        for (int i = 0; i <= V; i++) {
            graph.add(new ArrayList<>());
        }
        int E = Integer.parseInt(line[1]);
        for (int i = 0; i < E; i++) {
            line = br.readLine().split(" ");
            int from = Integer.parseInt(line[0]);
            int to = Integer.parseInt(line[1]);
            graph.get(from).add(to);
            inDegree[to]++;
        }

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

        for (int i = 1; i <= V; i++) {
            if (inDegree[i] == 0) {
                q.offer(i);
            }
        }

        while (!q.isEmpty()) {
            Integer from = q.poll();
            result.offer(from);

            for (Integer to : graph.get(from)) {
                inDegree[to]--;

                if (inDegree[to] == 0) {
                    q.offer(to);
                }
            }
        }

        while (!result.isEmpty()) {
            System.out.print(result.poll() + " ");
        }
    }
}