백준 14567번 <선수과목(Prerequisite)>

백준 알고리즘 14567번

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

14567번: 선수과목 (Prerequisite)

---

14567번

모든 과목에 대해 각 과목을 이수하려면 최소 몇 학기가 걸리는지 계산하여라.

 

입력으로 첫 줄에 과목의 수 N과 선수 조건의 수 M이 주어진다.

그 다음 M개의 줄에 걸쳐 선수 과목 조건이 주어지는데 이는 A B 형태이며, A번 과목이 B번 과목의 선수 과목이라는 의미이다.

 

출력으로 1번 과목 부터 N번 과목까지 차례대로 최소 몇 학기에 이수할 수 있는지 출력하면 된다.

---

문제 해결

위상정렬을 이용하여 해결할 수 있다.

미리 해야할 과목의 수를 저장한 in 배열과 이 과목을 끝내야 할 수 있는 과목들을 가진 subject ArrayList로 해결할 수 있다.

 

1. in 배열의 값이 0인 경우에 큐에 넣는다.
2. 큐에서 값 A를 꺼낸다.
   • A.value의 answer 값을 A.depth로 설정한다.
   • A.value가 선수 과목인 과목들의 in 배열 값에 -1을 한다.
   • 만약 그 과목들 중 in 배열 값이 0인 경우에 큐에 넣는다. -> 1번으로
3. 큐가 빌때까지 1-2번을 반복한다.

---

코드

package bj14567;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;

public class Main {
	static int[] answer;
	static ArrayList<ArrayList<Integer>> subjects;
	static int[] in;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] inArr = br.readLine().split(" ");
		int N = Integer.parseInt(inArr[0]);
		int M = Integer.parseInt(inArr[1]);

		in = new int[N + 1];
		answer = new int[N + 1];
		subjects = new ArrayList<>();

		for (int i = 0; i < N + 1; i++) {
			in[i] = 0;
			answer[i] = 0;
			subjects.add(new ArrayList<Integer>());
		}

		for (int i = 0; i < M; i++) {
			inArr = br.readLine().split(" ");
			int a = Integer.parseInt(inArr[0]);
			int b = Integer.parseInt(inArr[1]);

			in[b]++;
			subjects.get(a).add(b);
		}
		Queue<Tuple> queue = new LinkedList<>();
		int depth = 1;
		for (int i = 1; i < N + 1; i++) {
			if (in[i] == 0) {
				queue.add(new Tuple(i, depth));
			}
		}

		while (!queue.isEmpty()) {
			Tuple tuple = queue.poll();
			answer[tuple.value] = tuple.depth;
			ArrayList<Integer> t = subjects.get(tuple.value);
			int size = t.size();
			for (int i = 0; i < size; i++) {
				in[t.get(i)]--;
				if (in[t.get(i)] == 0) {
					queue.add(new Tuple(t.get(i), tuple.depth + 1));
				}
			}
		}

		for (int i = 1; i < N + 1; i++) {
			System.out.print(answer[i] + " ");
		}
	}

}

class Tuple {
	int value;
	int depth;

	public Tuple(int v, int d) {
		this.value = v;
		this.depth = d;
	}
}

---

결과

---