1766 - 문제집
본문
민오는 $1$번부터 $N$번까지 총 $N$개의 문제로 되어 있는 문제집을 풀려고 한다. 문제는 난이도 순서로 출제되어 있다. 즉 $1$번 문제가 가장 쉬운 문제이고 $N$번 문제가 가장 어려운 문제가 된다.
어떤 문제부터 풀까 고민하면서 문제를 훑어보던 민오는, 몇몇 문제들 사이에는 ‘먼저 푸는 것이 좋은 문제’가 있다는 것을 알게 되었다. 예를 들어 $1$번 문제를 풀고 나면 $4$번 문제가 쉽게 풀린다거나 하는 식이다. 민오는 다음의 세 가지 조건에 따라 문제를 풀 순서를 정하기로 하였다.
- $N$개의 문제는 모두 풀어야 한다.
- 먼저 푸는 것이 좋은 문제가 있는 문제는, 먼저 푸는 것이 좋은 문제를 반드시 먼저 풀어야 한다.
- 가능하면 쉬운 문제부터 풀어야 한다.
예를 들어서 네 개의 문제가 있다고 하자. $4$번 문제는 $2$번 문제보다 먼저 푸는 것이 좋고, $3$번 문제는 $1$번 문제보다 먼저 푸는 것이 좋다고 하자. 만일 $4-3-2-1$의 순서로 문제를 풀게 되면 조건 1과 조건 2를 만족한다. 하지만 조건 3을 만족하지 않는다. $4$보다 $3$을 충분히 먼저 풀 수 있기 때문이다. 따라서 조건 3을 만족하는 문제를 풀 순서는 $3-1-4-2$가 된다.
문제의 개수와 먼저 푸는 것이 좋은 문제에 대한 정보가 주어졌을 때, 주어진 조건을 만족하면서 민오가 풀 문제의 순서를 결정해 주는 프로그램을 작성하시오.
입력
첫째 줄에 문제의 수 $N$($1 \leq N \leq 32\,000$)과 먼저 푸는 것이 좋은 문제에 대한 정보의 개수 $M$($1 \leq M \leq 100\,000$)이 주어진다. 둘째 줄부터 $M$개의 줄에 걸쳐 두 정수의 순서쌍 $A,B$가 빈칸을 사이에 두고 주어진다. 이는 $A$번 문제는 $B$번 문제보다 먼저 푸는 것이 좋다는 의미이다.
항상 문제를 모두 풀 수 있는 경우만 입력으로 주어진다.
출력
첫째 줄에 문제 번호를 나타내는 $1$ 이상 $N$ 이하의 정수들을 민오가 풀어야 하는 순서대로 빈칸을 사이에 두고 출력한다.
제한
| 시간 제한 | 메모리 제한 |
|---|---|
| 2sec | 128MB |
풀이
3번 조건에 의해, 아무 선후관계가 없는 문제들을 풀 때는 번호순으로 풀면 된다. 다만 각 문제들에는 선후관계가 있어, 어떤 문제를 풀기 전에는 특정 문제를 풀 수 없는 경우가 있게 된다. 먼저 풀 수 있는 문제들이 존재하고, 지금 내가 풀 수 있는 문제들 중 가장 난이도가 쉬운 것들을 풀어나가야하는 문제라고 정리할 수 있을 것이다.
문제들의 선후관계가 존재하므로, 위상정렬을 통해 문제들의 선후관계는 해결할 수 있다. 그럼 지금 내가 풀 수 있는 문제들을 빠르게 솎아낼 수 있고, 그것들을 출력해나가면 2번 조건은 달성할 수 있다. 하지만 3번 조건이 있으므로, 우리가 지금 풀 수 있는 문제들 중 난이도가 가장 쉬운 것들을 찾아내야한다. 문제의 최대 수는 3만 2천개이므로, $O(N)$의 방법으로는 시간 초과가 날 것이다. 난이도는 문제의 번호와 같으므로 문제의 번호에 대한 우선순위 큐를 이용하면 $O(\log N)$의 시간으로 문제를 난이도 순으로 정렬할 수 있게 된다. 2가지 알고리즘을 융합해야 한다는 것.
코드
사용 언어 : C
최종 수정일 : 2023 / 10 / 14
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <stdio.h>
#include <stdlib.h>
typedef char bool;
const bool true = 1;
const bool false = 0;
#define MAX_IDX (32000 + 1)
typedef struct LinkNode {
int x;
struct LinkNode* next;
} LN;
int n, m;
LN* grid[MAX_IDX];
int deg[MAX_IDX];
int heap[MAX_IDX * 3], top;
LN* createNewNode(int x) {
LN* newNode = (LN*)malloc(sizeof(LN));
newNode->x = x;
newNode->next = NULL;
return newNode;
}
bool isHeapEmpty() { return (top == 0); }
void insertHeap(int x) {
heap[++top] = x;
int i = top;
while (i != 1 && heap[i / 2] > x) {
heap[i] = heap[i / 2];
heap[i / 2] = x;
i /= 2;
}
return;
}
int popHeap() {
int retval = heap[1];
heap[1] = heap[top--];
int i = 1, p = 2;
while (p < top) {
p += (heap[p] > heap[p + 1]);
if (heap[i] <= heap[p]) {
break;
}
int temp = heap[p];
heap[p] = heap[i];
heap[i] = temp;
i = p;
p *= 2;
}
if (p == top && heap[i] > heap[p]) {
int temp = heap[p];
heap[p] = heap[i];
heap[i] = temp;
}
return retval;
}
int main() {
scanf("%d %d", &n, &m);
while (m--) {
int a, b;
scanf("%d %d", &a, &b);
LN* newNode = createNewNode(b);
newNode->next = grid[a];
grid[a] = newNode;
++deg[b];
}
for (int i = 1; i <= n; ++i) {
if (deg[i] == 0) {
insertHeap(i);
}
}
while (!isHeapEmpty()) {
int x = popHeap();
printf("%d ", x);
LN* cur = grid[x];
while (cur != NULL) {
if (--deg[cur->x] == 0) {
insertHeap(cur->x);
}
cur = cur->next;
}
}
return 0;
}