문제
N개의 문제가 있고, 일부 문제는 다른 문제보다 먼저 풀어야 한다는 조건(선행 조건)이 M개 주어진다. 다음 두 조건을 만족하는 문제 풀이 순서를 구하는 문제이다.
- 먼저 풀어야 하는 문제가 있다면 그 문제를 먼저 풀어야 한다.
- 가능하다면 쉬운 문제(번호가 작은 문제)를 먼저 풀어야 한다.
입력
첫째 줄에 문제의 수 N(1 ≤ N ≤ 32,000)과 선행 조건의 수 M(1 ≤ M ≤ 100,000)이 주어진다. 다음 M줄에 A B 형식으로 A번 문제를 B번 문제보다 먼저 풀어야 한다는 조건이 주어진다.
출력
문제 풀이 순서를 공백으로 구분하여 출력한다.
예제
| 입력 | 출력 |
|---|---|
4 2 4 2 3 1 | 3 1 4 2 |
풀이
위상 정렬(Topological Sort)에 우선순위 큐(최소 힙)를 결합하여, 진입 차수가 0인 노드 중 번호가 작은 것을 먼저 처리한다.
- 각 문제의 진입 차수(indegree)를 계산하고, 인접 리스트로 그래프를 구성한다.
- 진입 차수가 0인 노드를
PriorityQueue(최소 힙)에 삽입한다. - 힙에서 가장 작은 번호의 문제를 꺼내 결과에 추가한다.
- 해당 문제의 이웃 노드들의 진입 차수를 1 감소시키고, 진입 차수가 0이 된 노드를 힙에 삽입한다.
- 힙이 빌 때까지 반복한다.
핵심 아이디어: 표준 위상 정렬에서 큐(FIFO) 대신 우선순위 큐(최소 힙)를 사용하면, 진입 차수가 0인 노드 중 항상 번호가 가장 작은 것을 선택하므로 두 번째 조건(번호가 작은 것을 먼저)을 자동으로 만족한다.
코드
package com.ssafy.an.day149;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;
import java.util.StringTokenizer;
public class Day148BOJ1766위상정렬 {
static int N, M;
static int[] indegree;
static List<Integer>[] graph;
@SuppressWarnings("unchecked")
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
M = Integer.parseInt(st.nextToken());
indegree = new int[N + 1];
graph = new List[N + 1];
for (int i = 0; i < N + 1; i++)
graph[i] = new ArrayList<>();
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int from = Integer.parseInt(st.nextToken());
int to = Integer.parseInt(st.nextToken());
graph[from].add(to);
indegree[to] += 1;
}
PriorityQueue<Integer> PQ = new PriorityQueue<>();
for (int i = 1; i <= N; i++) {
if (indegree[i] == 0) {
PQ.offer(i);
}
}
StringBuilder sb = new StringBuilder();
while (!PQ.isEmpty()) {
int num = PQ.poll();
sb.append(num + " ");
for (int n : graph[num]) {
indegree[n] -= 1;
if (indegree[n] == 0) {
PQ.offer(n);
}
}
}
System.out.println(sb.toString());
br.close();
}
}복잡도
- 시간: O((N + M) log N) — 위상 정렬 O(N + M) + 우선순위 큐 연산 O(N log N)
- 공간: O(N + M)