[백준] 1766 : 문제집

문제

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

 

 

• N개의 문제(1번~N번)가 있고, 일부 문제는 다른 문제를 먼저 풀어야 한다.
• 가능한 한 쉬운 문제부터 풀어야 한다.
• 즉, 진입 차수가 0인 노드 중에서 번호가 작은 문제부터 풀어야 한다.

 

 

입출력

입력 

4 2
4 2
3 1

 

출력

3 1 4 2

---

아이디어

 

위상정렬 + 우선순위 큐 

위상 정렬(Topological Sorting)을 사용하여 순서를 정하면서, 가능한 한 숫자가 작은 문제 부터 풀기 위해 우선순위 큐를 활용한다 

 

1. 그래프, 진입 차수 배열 생성

2. 진입 차수가 0인 문제를 우선순위 큐에 저장 (문제 번호가 작은 것부터 풀어야하므로 오름차순 정렬이 필요)

 

 

코드 

 

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
	static int N, M; // 문제의 수, 먼저 푸는 것이 좋은 문제에 대한 정보의 개수
	static List<Integer>[] adj;
	static int[] indegree;

	public static void main(String[] args) throws Exception {
		System.setIn(new FileInputStream("src/input.txt"));
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken()); // 문제의 수
		M = Integer.parseInt(st.nextToken()); // 먼저 푸는 것이 좋은 문제에 대한 정보의 개수

		adj = new ArrayList[N + 1];
		for (int n = 0; n < N + 1; n++) {
			adj[n] = new ArrayList<>();
		}
		indegree = new int[N + 1];
		for (int m = 0; m < M; m++) {
			st = new StringTokenizer(br.readLine());
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
			adj[A].add(B); // A -> B
			indegree[B]++;
		}

		boolean[] visited = new boolean[N + 1];
		// 쉬운 문제 먼저 -> 진입 차수가 0인 노드 중에서 번호가 작은 문제부터 풀기
		// 따라서, PriorityQueue 사용
		PriorityQueue<Integer> queue = new PriorityQueue<>();
		for (int i = 1; i <= N; i++) {
			if (indegree[i] == 0) {
				queue.add(i);
				visited[i] = true;
			}
		}

		while (!queue.isEmpty()) {
			int now = queue.poll();
			System.out.print(now + " ");
			for (int next : adj[now]) {
				if (visited[next]) {
					continue;
				}
				indegree[next] -= 1;
				if (indegree[next] == 0) {
					visited[next] = true;
					queue.add(next);
				}
			}
		}

	}

}