[백준][BOJ-14567][자바] 선수과목

www.acmicpc.net/problem/14567

14567번: 선수과목 (Prerequisite)

import java.io.*;
import java.util.*;

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[] topological = new int[N];
		int[] order = new int[N];
		List<Integer>[] list = new List[N];
		
		for(int i=0; i<N; i++) {
			list[i] = new ArrayList<>();
		}
		
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken())-1;
			int end = Integer.parseInt(st.nextToken())-1;
			
			list[start].add(end);
			topological[end]++;
		}
		
		// 위상정렬
		Queue<Integer> qu = new LinkedList<Integer>();
		
		// 초기 진입0인 정점 넣어주기
		for(int i = 0; i<N; i++) {
			if (topological[i] == 0) {
				qu.offer(i);
				order[i]++;
			}
		}
		
		for (int i = 0; i < N; i++) {
			// 정점을 다 방문 하기 전에 큐가 빈다면 사이클 발생
			if (qu.isEmpty()) break;
			
			int curr = qu.poll();
			int size = list[curr].size();
			List Edge = list[curr];
			
			for (int j=0; j<size; j++) {
				int vertex = (int) Edge.get(j);
				topological[vertex]--;
				
				if(topological[vertex] == 0) {
					qu.offer(vertex);
					if(order[vertex] < order[curr]+1) order[vertex] = order[curr]+1;
				}
			}
		}
		
		for(int i=0; i<order.length; i++) {
			System.out.print(order[i]+" ");
		}
	}
}

정리

1. 인접 리스트로 진출과 진입 정보들을 저장하였다.
2. 각 정점마다 진입되는 간선들의 개수를 Update 한다.
3. 초기 진입 값이 0인 정점들을 Queue에 넣어준다.
4. 큐에서 정점을 꺼내서 해당 정점이 향하고 있는 간선들을 삭제시켜준다. (topological[vertex]--)
5. 정점의 진입이 0이 된다면 큐에 넣어준다.
6. order배열을 통해 연결하고 있었던 정점들의 값 중에 제일 큰 값을 +1 해서 저장하면 최소 몇 학기가 걸리는지 알 수 있다.