BOJ_줄 세우기_2252

문제 링크

성능 요약

메모리: 45460 KB, 시간: 420 ms

분류

방향 비순환 그래프, 그래프 이론, 위상 정렬

제출 일자

2025년 1월 14일 10:28:56

문제 설명

N명의 학생들을 키 순서대로 줄을 세우려고 한다. 각 학생의 키를 직접 재서 정렬하면 간단하겠지만, 마땅한 방법이 없어서 두 학생의 키를 비교하는 방법을 사용하기로 하였다. 그나마도 모든 학생들을 다 비교해 본 것이 아니고, 일부 학생들의 키만을 비교해 보았다.

일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 프로그램을 작성하시오.

입력

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

학생들의 번호는 1번부터 N번이다.

출력

첫째 줄에 학생들을 앞에서부터 줄을 세운 결과를 출력한다. 답이 여러 가지인 경우에는 아무거나 출력한다.

느낀점

• 위상정렬 출력 문제 같다는 게 금방 느껴져서 비교적 빠르게 풀렸다.
• Intellij에서 사용하고 있는 AutoCP의 채점 프로그램에서 List의 배열이 안정적이지 않은 것에 대해 민감하게 오류를 발생시켜서, @SuppressWarnings("unchecked")를 계속 붙여주고 있지만 백준에서 채점 돌릴때는 없어도 문제없다.
• 제네릭을 배열화 하면 안전하지 않기 때문에 발생하는 에러인데, 적절한 값만 사용될 것을 개발자가 보장할 경우 해당 어노테이션을 붙여서 경고 발생을 억제하는 것이다.

설계 : 5분

• 뒷순서로 올 다음 학생을 기록하는 List[] adj와 앞에 필수적으로 서야할 학생의 수를 기록할 int[] enter를 준비한다.
• 모두 입력되면 enter를 순회하며 값이 0인 인덱스를 Queue에 넣는다.
• Queue에서 값을 하나씩 뽑아 출력하고, 다음순서인 학생들에게서 enter값을 -1해준다.
• -1을 한 값이 0인 학생들은 Queue에 넣는다.
• Queue가 빌 때까지 반복한다.

코드(Java)

• 구현 시간: 15분

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 줄 세우기_2252
 * Date: 2025.01.14
 */

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

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;

  @SuppressWarnings("unchecked")
	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		st = new StringTokenizer(br.readLine(), " ");
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int[] enter = new int[n+1];
        List<Integer>[] adj = new List[n+1];
        for (int i = 0; i <= n; i++) adj[i] = new ArrayList<>();

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int before = Integer.parseInt(st.nextToken());
            int after = Integer.parseInt(st.nextToken());

            enter[after]++;
            adj[before].add(after);
        }

        Queue<Integer> queue = new ArrayDeque<>();
        for (int i = 1; i <= n; i++) {
            if (enter[i] == 0) queue.offer(i);
        }

        StringBuilder sb = new StringBuilder();
        while (!queue.isEmpty()) {

            int curr = queue.poll();
            sb.append(curr).append(" ");

            for (int next : adj[curr]) {
                if (--enter[next] == 0) queue.offer(next);
            }
        }

        bw.write(sb.toString());
		bw.flush();
		bw.close();
		br.close();
	}
}