[Java] 백준 14567 - 선수과목

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

14567번: 선수과목 (Prerequisite)

 

위상정렬로 풀어야 할 것 같은 느낌이 확 ! 오는 문제

 

매번 선행과목 수가 더 이상 없을 경우 부터 처리해주기 때문에,

선행과목 수를 저장할 1차원 배열을 선언해준다 (int[] degree)

 

그리고 degree의 값이 0인 경우를 큐에 넣고, 해당 과목을 선행과목으로 두었던 다른 과목의 degree를 감소시킨다.

위 과정을 반복!

 

 

 

[코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.HashSet;
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));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int[] degree = new int[N+1];
		
		HashSet<Integer>[] next = new HashSet[N+1];
		HashSet<Integer> hs = new HashSet<>();
		int[] fin = new int[N+1];
		
		for(int i=1; i<=N; i++) {
			next[i] = new HashSet<>();
			hs.add(i);
		}
			
		
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken()), b = Integer.parseInt(st.nextToken());
			next[a].add(b); degree[b]++;
		}	
		
		int cnt = 1;
		while(hs.size()>0) {
			HashSet<Integer> rm = new HashSet<>();
			for(int i : hs) {
				//System.out.println(i);
				if(degree[i]==0) {
					fin[i]=cnt;
					rm.add(i);
				}
			}
			//System.out.println(hs.size());
			
			for(int now : rm) {
				hs.remove(now);
				for(int nexts : next[now]) {
					degree[nexts]--;
				}
			}
			
			cnt++;
		}
			
		StringBuilder sb = new StringBuilder();
		for(int i=1; i<=N; i++)
			sb.append(fin[i]+" ");
		
		System.out.println(sb.toString().trim());
		
	}
}