[백준(Baekjoon)][자바(java)] 1766 : 문제집 / 위상 정렬

 

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

1766번: 문제집

 

문제 풀이

 

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

public class Main {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken()), i, u, v;
		List<List<Integer>> edge_out = new ArrayList<>();
		for (i = 0; i < n; ++i)
			edge_out.add(new ArrayList<>());
		int degree_in[] = new int[n];
		for (i = 0; i < m; ++i) {
			st = new StringTokenizer(br.readLine());
			u = Integer.parseInt(st.nextToken()) - 1;
			v = Integer.parseInt(st.nextToken()) - 1;
			edge_out.get(u).add(v);
			degree_in[v]++;
		}
		br.close();
		PriorityQueue<Integer> top = new PriorityQueue<>(); //TreeSet<Integer> top = new TreeSet<>();
		for (i = 0; i < n; ++i)
			if (degree_in[i] == 0)
				top.add(i);
		StringBuilder sb = new StringBuilder();
		int t = 0;
		while (t++ < n) {
			u = top.remove(); //u = top.pollFirst();
			sb.append((u + 1) + " ");
			for (int vv : edge_out.get(u)) {
				degree_in[vv]--;
				if (degree_in[vv] == 0)
					top.add(vv);
			}
		}
		System.out.println(sb.toString());
	}
}

 

-  선택할 수 있는 여러 개의 정점들 중 번호가 더 작은 것을 우선으로 택해야 한다는 조건이 있으므로
   우선순위 큐를 이용하여 선택 가능한 정점들의 번호를 담음

( 2252 줄 세우기 문제와 풀이가 유사(나는 동일).
 이 문제는 여러 개의 정답 모두 인정하므로 우선순위 큐 대신 그냥 리스트 이용해도 됨
 https://hyunjiishailey.tistory.com/482?category=381511 )

※  위상 정렬에 대한 설명  ( https://hyunjiishailey.tistory.com/361?category=381527 )