[Java] 백준 2252번 줄 세우기

위상정렬 문제입니다.

각 학생별로 누가 더 키가 큰지에 대한 정보를 입력받습니다.
모든 학생별로 키가 큰지에 대한 정보를 받지는 않습니다.
받은 정보를 사용해서 여러가지 답안 중 하나를 출력하면 됩니다.

a와 b가 입력을 받으면 a>b인 경우인데 이 때 a의 배열에 b를 추가해줍니다.
이렇게 전부 추가해주면서 size배열을 만들어서 b의 사이즈를 늘려줍니다.

size가 0인곳들은 자신보다 큰 관계가 없는 곳입니다.
0인곳들을 큐에 넣어서 BFS로 탐색을 했습니다.

size가 1인곳을 방문하면 그대로 큐에 담아서 진행합니다.
size가 2이상인곳은 아직 그 사람보다 큰 곳이 오지 않았기 때문에 size를 1 줄여주고 큐에 넣지 않습니다.

문제에서 싸이클이 발생하지 않기 때문에 해당 부분에 대한 처리는 하지 않았습니다.

 

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		int[] size = new int[n + 1];
		Queue<Integer> q = new LinkedList<>();
		ArrayList<ArrayList<Integer>> al = new ArrayList<>();

		for (int i = 0; i <= n; ++i) {
			ArrayList<Integer> temp = new ArrayList<>();
			al.add(temp);
		}

		for (int i = 0; i < m; ++i) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			al.get(a).add(b);
			++size[b];
		}

		for (int i = 1; i <= n; ++i) {
			if (size[i] == 0) {
				q.add(i);
			}
		}

		while (!q.isEmpty()) {
			int index = q.poll();
			if (size[index] > 1) {
				--size[index];
				continue;
			}
			bw.write(index + " ");
			for (int i = 0; i < al.get(index).size(); ++i) {
				q.add(al.get(index).get(i));
			}
		}

		bw.close();
	}
}