[BaekJoon] 2252 줄 세우기 (Java)

1.  문제 링크

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

2.  문제

요약

• N명의 학생들을 키 순서대로 줄을 세우려고 하는데 두 학생의 키를 비교하는 방법을 사용합니다.
• 모든 학생들을 다 비교해본 것이 아니고, 일부 학생들의 키만을 비교해 보았습니다.
• 일부 학생들의 키를 비교한 결과가 주어졌을 때, 줄을 세우는 문제입니다.
• 입력: 첫 번째 줄에 1보다 크거나 같고 32,000보다 작거나 같은 N과 1보다 크거나 같고 100,000보다 작거나 같은 키를 비교한 횟수인 M이 주어지고 두 번째 줄부터 M개의 줄에는 키를 비교한 두 학생의 번호 A, B가 주어집니다. 이는 학생 A가 학생 B의 앞에 서야 한다는 의미입니다.
  • 학생들의 번호는 1번부터 N번입니다.
• 출력: 첫 번째 줄에 학생들을 앞에서부터 줄을 세운 결과를 출력합니다. 답이 여러 가지인 경우에는 아무거나 출력합니다.

3.  소스코드

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N, M;
	static int[] precedeNum;
	static HashMap<Integer, ArrayList<Integer>> precede;
	static void input() {
		Reader scanner = new Reader();
		N = scanner.nextInt();
		M = scanner.nextInt();
		precedeNum = new int[N + 1];
		precede = new HashMap<Integer, ArrayList<Integer>>();
		for(int num = 1; num <= N; num++) precede.put(num, new ArrayList<Integer>());
		for(int count = 0; count < M; count++) {
			int first = scanner.nextInt();
			int second = scanner.nextInt();
			precedeNum[second]++;
			precede.get(first).add(second);
		}
	}
	
	static void solution() {
		Queue<Integer> queue = new LinkedList<Integer>();
		for(int num = 1; num <= N; num++) {
			if(precedeNum[num] == 0) {
				queue.offer(num);
				sb.append(num).append(' ');
			}
		}
		while(!queue.isEmpty()) {
			int curStudent = queue.poll();
			for(int student : precede.get(curStudent)) {
				precedeNum[student]--;
				if(precedeNum[student] == 0) {
					queue.offer(student);
					sb.append(student).append(' ');
				}
			}
		}
		System.out.println(sb);
	}
	
	public static void main(String[] args) {
		input();
		solution();
	}
	
	static class Reader {
		BufferedReader br;
		StringTokenizer st;
		public Reader() {
			br = new BufferedReader(new InputStreamReader(System.in));
		}
		String next() {
			while(st == null || !st.hasMoreElements()) {
				try {
					st = new StringTokenizer(br.readLine());
				} catch(IOException e) {
					e.printStackTrace();
				}
			}
			return st.nextToken();
		}
		int nextInt() {
			return Integer.parseInt(next());
		}
	}
}