[백준 1766] 문제집 - JAVA

문제 링크

문제 정의

• 1번부터 $N$번 까지의 문제집 존재
• 일반적으로 1번이 가장 쉽고 $N$번이 가장 어려운 문제
• 몇몇 문제는 먼저 푸는 문제가 존재 (3 가지 조건이 있다)
  • $N$개의 문제는 모두 풀어야 한다.
  • 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.
  • 가능하면 쉬운 문제부터 풀어야 한다.

---

접근 방법

우선 처음 볼 때는 기존 위상정렬과 다를바가 없어보이는데
이 문제에는 약간의 함정이 존재합니다.

진입 차수가 동일하더라도 푸는 문제의 순서는 정해짐

이게 무슨 소리냐 하면
만약 1 ~ 10까지 문제가 존재하고
먼저 풀어야 할 문제가 없는2 3 5가 존재한다고 가정한다면
여기에서도 푸는 우선순위가 존재합니다.

일반적으로 1번이 가장 쉽고 $N$번이 가장 어려운 문제

이 조건에 의해 순서는 숫자의 크기 순서대로 2 3 5가 됩니다.

---

중간에 끼어들기 존재

진입 차수가 0인 2 4 5가 존재하고
2번 문제를 풀면 3번 문제를 풀 수 있다고 가정할 때

2번 문제를 푸는 순간
3번 문제의 진입 차수가 0이 됩니다.

그러면 그 순간 풀어야할 문제의 우선순위가 바뀌게 되는데
그 순서는 3 4 5가 됩니다.

그렇기 때문에 기존의 큐를 사용해서는 해당 문제를 풀 수 없다고 판단했습니다.

우선순위 큐 적용 이유

즉 진입 차수가 0이 되는 순간 우선순위를 갱신할 수 있는 자료구조가 필요한데
우선순위 큐가 삽입과 삭제가 $O(logN)$의 시간 복잡도로
현재 입력의 최대 범위인 $N = 32000$을 충분히 해결할 수 있는
가장 최적의 자료구조라고 생각되어서
우선순위 큐를 적용해서 문제를 풀게 되었습니다.

---

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;


class Node {
	int next;
	Node node;

	public Node (int next, Node node) {
		this.next = next;
		this.node = node;
	}
}

public class Main {
	static StringTokenizer st;
	static Node[] graph;
	static int[] in;
	static int N;
	static int M;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		in = new int[N+1];
		graph = new Node[N+1];

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());
		
			graph[A] = new Node(B, graph[A]);
			in[B]++;
		}

		System.out.println(topologySort());
	}

	private static String topologySort() {
		StringBuilder sb = new StringBuilder();
		PriorityQueue<Integer> pq = new PriorityQueue<>();

		for (int v = 1; v <= N; v++) {
			if (in[v] == 0) {
				pq.offer(v);
			}
		}

		while (!pq.isEmpty()) {
			int v = pq.poll();
			sb.append(v).append(" ");

			for (Node node = graph[v]; node != null; node = node.node) {
				int nv = node.next;
				if (--in[nv] == 0) pq.offer(nv);
			}
		}

		return sb.toString();
	}
}