백준 14567번 : 선수과목 (Prerequisite) (Java)

 문제

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

14567번: 선수과목 (Prerequisite)

14567 선수과목

 

 구현 방법

위상 정렬의 대표적인 문제입니다🥶

위상 정렬 (Topology Sort) 이란 방향 그래프에 존재하는 각 정점들의 선행 순서를 배신하지 않으면서 모든 정점을 나열하는 것 입니다.

 

bfs를 이용한 위상정렬의 기본적인 해결 방법 입니다.

1. 진입 차수가 0인 정점을 큐에 저장

2. 선택된 정점과 부속된 간선 삭제

3. 모든 정점이 선택되거나 삭제 될 때까지 위 과정 반복

 

여기에 이수 학기를 계산해야 했기 때문에 과정을 반복할 때 큐의 사이즈로 레벨을 카운트하여 저장했습니다.

 

 구현 코드

package BOJ.Gold;

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

public class B14567_선수과목 {
	static int N, M, inDegree[], size, cnt, ans[];
	static List<List<Integer>> list = new ArrayList<>();
	static Queue<Integer> queue = new LinkedList<>();
	static StringBuilder sb = new StringBuilder();
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		for (int i=0;i<=N;i++) {
			list.add(new ArrayList<>());
		}
		inDegree = new int[N+1];
		ans = new int[N+1];
		for (int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine());
			int v1 = Integer.parseInt(st.nextToken());
			int v2 = Integer.parseInt(st.nextToken());
			list.get(v1).add(v2); // 간선 저장
			inDegree[v2]++; // 진입 차수 저장
		}
		topology();
		for (int i=1;i<=N;i++) {
			sb.append(ans[i]+" ");
		}
		System.out.println(sb);
	}
	
	static void topology() {
		for (int i=1;i<=N;i++) {
			if (inDegree[i] == 0) queue.offer(i); // 집입 차수가 0이다 == 바로 이수할 수 있다
		}
		cnt = 1; // 학기를 카운트 할 변수
		while(!queue.isEmpty()) {
			size = queue.size();
			while(size-->0) {
				int v = queue.poll(); // 선택된 정점 뽑기
				ans[v] = cnt; // 이수 학기 저장
				for (int next : list.get(v)) { // 내가 이동할 수 있는 간선 리스트
                	// 부속된 간선 삭제 == 내가 이동할 간선의 진입 차수 -1 (내가 빠졌으니)
					if (--inDegree[next] == 0) queue.offer(next);
				}
			}
			cnt++; // 한 번 돌 때마다 한 학기씩 증가
		}
	}
}

 

정답!