백준 2252 줄 세우기

Algorithm

백준 2252 줄 세우기

dalooong 2023. 7. 18. 09:24

2252번: 줄 세우기

첫째 줄에 N(1 ≤ N ≤ 32,000), M(1 ≤ M ≤ 100,000)이 주어진다. M은 키를 비교한 회수이다. 다음 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어진다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의

www.acmicpc.net

문제코드

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

public class boj2252 {
    public void solution() throws IOException {
    BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer infoToken = new StringTokenizer(reader.readLine());
    int students = Integer.parseInt(infoToken.nextToken());
    int compares = Integer.parseInt(infoToken.nextToken());

    List<List<Integer>> adjList = new ArrayList<>();
        for (int i = 0; i < students + 1; i++) {
        adjList.add(new ArrayList<>());
    }

        for (int i = 0; i <compares; i++) {
        StringTokenizer edgeToken = new StringTokenizer(reader.readLine());
        int start = Integer.parseInt(edgeToken.nextToken());
        int end = Integer.parseInt(edgeToken.nextToken());
        adjList.get(start).add(end);
    }
    // 1. 진입 차수 정리
    int[] inDegrees = new int[students + 1];
        for (List<Integer> neighbors: adjList) {
        for (int neighbor: neighbors) {
            inDegrees[neighbor]++;
        }
    }

    // 2. 진입 차수에 따른 첫 정점 정하기
    Queue<Integer> queue = new LinkedList<>();
        for (int i = 1; i < students + 1; i++) {
        if (inDegrees[i] == 0) queue.offer(i);
    }

    // 3. Queue 를 이용 위상정렬 진행
    List<Integer> result = new ArrayList<>();
        while (!queue.isEmpty()) {
        int node = queue.poll();
        result.add(node);
        for (int neighbor: adjList.get(node)) {
            inDegrees[neighbor]--;
            if (inDegrees[neighbor] == 0) queue.offer(neighbor);
        }
    }

    // 정답 출력
    StringBuilder answer = new StringBuilder();
        for (int node: result) answer.append(node).append(' ');
        System.out.println(answer);
}

    public static void main(String[] args) throws IOException {
        new boj2252().solution();
    }
}

출력 결과