문제 출처
https://www.acmicpc.net/problem/1766
해당 문제는 위상정렬을 이용하여 풀 수 있는 문제.
문제간에는 우선순위가 있어서 먼저 푸는것이 좋은 문제의 경우 먼저 풀어야(방문) 한다.
단, 풀 수 있는 문제가 여러개인 경우 (indegree가 0 인 문제가 여러개인 경우) 문제 번호가 낮은 것이 더 쉬운 문제이므로 먼저 풀어야(방문) 한다.
// 위상정렬 4
// Priority Queue 사용
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.Queue;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Main {
public static void main(String[] args) throws Exception{
//System.setIn(new FileInputStream("src/input.txt"));
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st.nextToken());
int K = Integer.parseInt(st.nextToken());
ArrayList<Integer>[] list = new ArrayList[N+1];
for(int i=1; i<=N; i++) {
list[i] = new ArrayList<Integer>();
}
int v1, v2;
int indegree[] = new int[N+1];
boolean visited[] = new boolean[N+1];
for(int i=1; i<=K; i++) {
st = new StringTokenizer(br.readLine());
v1 = Integer.parseInt(st.nextToken());
v2 = Integer.parseInt(st.nextToken());
list[v1].add(v2);
indegree[v2]++;
}
// 작은 숫자가 먼저 나오도록!!
PriorityQueue<Integer> q = new PriorityQueue<Integer>(new Comparator<Integer>() {
@Override
public int compare(Integer a, Integer b) {
return a - b;
}
});
for(int i=1; i<=N; i++) {
if(indegree[i] == 0) {
q.add(i);
}
}
int now;
while(!q.isEmpty()) {
now = q.poll();
visited[now] = true;
System.out.print(now+" ");
for(int next : list[now]) {
indegree[next]--;
if(indegree[next] == 0) {
q.add(next);
}
}
}
}
}
댓글