[BOJ/Java] 2252. 줄 세우기

[BOJ/Java] 2252. 줄 세우기

 

2252번: 줄 세우기

---

풀이

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

public class Main {
    int n, m;
    public static void main(String[] args) throws IOException {
        new Main().io();
    }

    private void io() throws IOException {
        // 입력을 받기 위한 BufferedReader와 출력을 위한 BufferedWriter 선언
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringBuilder sb = new StringBuilder();

        // 첫 번째 줄에서 학생의 수 N과 키를 비교한 회수 M을 입력 받음
        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        m = Integer.parseInt(st.nextToken());

        // 각 학생의 진입차수를 저장할 배열과 각 학생들의 비교 정보를 저장할 리스트를 생성
        int[] indegree = new int[n + 1];
        List<List<Integer>> arrayList = new ArrayList<>();
        for (int i = 0; i < n+1; i++) {
            arrayList.add(new ArrayList<>());
        }

        // 키를 비교한 정보를 입력 받고, 진입차수 배열과 리스트에 정보 저장
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int v1 = Integer.parseInt(st.nextToken());
            int v2 = Integer.parseInt(st.nextToken());
            arrayList.get(v1).add(v2); // v1이 v2보다 앞에 서야 함
            indegree[v2]++; // v2의 진입차수 증가
        }

        // 위상 정렬을 수행하여 정렬된 순서의 결과를 큐로 받아옴
        Queue<Integer> ans = topologicalSort(indegree, arrayList);

        // 결과를 StringBuilder에 추가
        for (int a : ans) {
            sb.append(a + " ");
        }

        // 결과 출력
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }

    // 위상 정렬 수행
    private Queue<Integer> topologicalSort(int[] indegree, List<List<Integer>> array) {
        Queue<Integer> queue = new LinkedList<>();
        Queue<Integer> result = new LinkedList<>();

        // 진입차수가 0인 학생들을 큐에 삽입
        for (int i = 1; i <= n; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }

        // 큐가 빌 때까지 반복
        while (!queue.isEmpty()) {
            int idx = queue.poll(); // 큐에서 학생 번호를 꺼냄
            result.offer(idx); // 결과 큐에 추가

            // 현재 학생과 연결된 학생들의 진입차수를 감소시키고, 진입차수가 0이 되면 큐에 삽입
            for (int i : array.get(idx)) {
                indegree[i]--; // 연결된 학생의 진입차수 감소

                if (indegree[i] == 0) {
                    queue.offer(i); // 진입차수가 0이 되면 큐에 삽입
                }
            }
        }

        // 정렬된 결과 반환
        return result;
    }
}