boj 1766: 문제집

1번부터 N번까지 총 N개의 문제로 되어 있는 문제집을 풀려고 한다. 문제는 난이도 순서로 출제되어 있다.

문제들 사이에는 '먼저 푸는 것이 좋은 문제'가 있다. 예를 들어 1번 문제를 풀고 나면 4번 문제가 쉽게 풀린다거나 하는 식이다.

 

문제 조건

1. N개의 문제는 모두 풀어야 한다.
2. 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.
3. 가능하면 쉬운 문제부터 풀어야 한다.

이 문제는 순서가 있다. 기본적으로 위상정렬을 이용 + 크기순으로 순회하면 될 것이라고 생각했다.

크기순으로 순회하기 위해서 PriorityQueue를 사용하도록 했다. 풀이는 아래와 같다.

import java.util.*;

public class Main {

	public static void main(String[] args) {
		Scanner in = new Scanner(System.in);
		int v = in.nextInt();
		int e = in.nextInt();

		LinkedList<Integer> childs[] = new LinkedList[v + 1];
		LinkedList<Integer> parents[] = new LinkedList[v + 1];
		for (int i = 1; i <= v; i++) {
			childs[i] = new LinkedList<Integer>();
			parents[i] = new LinkedList<Integer>();
		}

		int[] parentNum = new int[v + 1];

		for (int i = 0; i < e; i++) {
			int parentNode = in.nextInt();
			int childNode = in.nextInt();

			childs[parentNode].add(childNode);
			parents[childNode].add(parentNode);
			parentNum[childNode]++;
		}

		traverseProblems(parentNum, childs, parents);
	}

	public static void traverseProblems(int[] parentNum, LinkedList<Integer> childs[], LinkedList<Integer> parents[]) {
		int problemNum = parentNum.length;
		boolean[] isVisited = new boolean[problemNum];

		PriorityQueue<Integer> queue = new PriorityQueue<Integer>();
		for (int i = 1; i < problemNum; i++) {
			if (parentNum[i] == 0) {
				queue.add(i);
			}
		}

		while (!queue.isEmpty()) {
			int now = queue.poll();
			isVisited[now] = true;
			System.out.print(now + " ");

			for (int node : childs[now]) {
				parentNum[node]--;

				if (!isVisited[node] && parentNum[node] == 0) {
					queue.add(node);
				}
			}
		}
	}
}