1번부터 n번까지 번호가 붙은 일 n개가 있다. 조건 m개가 주어지며, 조건 하나 "a b"는 a번 일을 끝낸 뒤에야 b번 일을 할 수 있다는 뜻이다. 같은 조건이 여러 번 주어질 수도 있다. 일은 한 번에 하나씩 하며, 모든 일을 한 번씩 한다. 매번, 먼저 해야 할 일이 모두 끝나 지금 할 수 있는 일 가운데 번호가 가장 작은 일을 한다. 이렇게 했을 때 일을 하는 차례를 빈칸으로 나눠 한 줄에 출력하라. 조건 때문에 일들이 서로를 기다려서 모든 일을 다 할 수 없으면 -1만 출력한다.
5 4 3 1 3 2 5 4 2 4
3 1 2 5 4
3 3 1 2 2 3 3 1
-1
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
일마다 '아직 안 끝난 앞선 일의 수'(waiting, 들어오는 화살표 수)를 세고, 0인 일부터 꺼내며 그 뒤의 일들의 수를 하나씩 줄여요.
0이 된 일은 할 수 있는 일 모음에 넣어요(위상 정렬, 칸(Kahn) 알고리즘 — 너비 우선 탐색처럼 퍼져요).
모음에서 늘 가장 작은 번호를 꺼내야 하니(욕심) 보통 큐가 아니라 최소 힙(우선순위 큐)이 필요해요: 보통 큐(먼저 넣은 것부터)도 조건은 지키지만 "6 1, 5 2, 4 3"에서 4 5 6 3 2 1을 내요(답 4 3 5 2 6 1).
매번 모든 일을 훑어 가장 작은 것을 찾으면 n² = 1억 번이라 크레이콘은 실행 걸음 한도(약 5천만)를 넘어요.
고리가 있으면 그 안의 일은 waiting이 끝내 0이 되지 않으니, 꺼낸 일이 n개보다 적으면 -1이에요 — 확인하지 않으면 일부 순서만 내요.
같은 조건이 여러 번 오면 인접 목록에도 여러 번 넣어야 waiting과 맞아요(한쪽만 중복을 지우면 영영 0이 안 돼요).
최소 힙은 언어마다 달라요: Python heapq(목록에 heappush·heappop, 최소 힙), Java PriorityQueue<Integer>(기본이 최소), C# PriorityQueue<int, int>(.NET 6부터, 값과 우선순위를 따로 넣어요: Enqueue(t, t)), C++ std::priority_queue는 기본이 최대 힙이라 std::greater<int>를 줘야 해요.
JavaScript·TypeScript·C·크레이콘은 힙이 없어서 목록으로 직접 만들어요: i의 부모는 (i - 1) / 2(정수 나눗셈 — JavaScript >> 1, 크레이콘 수학.몫(i - 1, 2)), 자식은 2i + 1·2i + 2.
TypeScript는 pop()이 number | undefined라 비어 있지 않을 때 !를 붙여요.
크레이콘은 목록이 10,000칸까지라 번호에서 1을 빼 0번부터 담고, 출력은 목록을 콘솔.쓰기(order)로 쓰면 빈칸으로 이어 써요.
import heapqimport sys data = sys.stdin.read().split()n, m = int(data[0]), int(data[1]) after = [[] for _ in range(n + 1)] # after[a] = a를 끝내야 할 수 있는 일들waiting = [0] * (n + 1) # waiting[b] = b보다 먼저 끝내야 하는데 아직 안 끝난 일의 수for i in range(m): a, b = int(data[2 + 2 * i]), int(data[3 + 2 * i]) after[a].append(b) waiting[b] += 1 # 지금 할 수 있는 일들을 최소 힙에 두고, 늘 가장 작은 번호를 꺼낸다ready = [t for t in range(1, n + 1) if waiting[t] == 0]heapq.heapify(ready)order = []while ready: t = heapq.heappop(ready) order.append(t) for nxt in after[t]: waiting[nxt] -= 1 if waiting[nxt] == 0: heapq.heappush(ready, nxt) # 고리(순환)가 있으면 그 안의 일은 waiting이 0이 되지 않아 끝까지 남는다print(" ".join(map(str, order)) if len(order) == n else -1)const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, m] = data; // 최소 힙: heap[0]이 가장 작고, i의 자식은 2i+1, 2i+2class MinHeap { constructor() { this.items = []; } get size() { return this.items.length; } push(x) { const a = this.items; a.push(x); let i = a.length - 1; while (i > 0) { const parent = (i - 1) >> 1; if (a[parent] <= a[i]) break; [a[parent], a[i]] = [a[i], a[parent]]; i = parent; } } pop() { const a = this.items; const top = a[0]; const last = a.pop(); if (a.length > 0) { a[0] = last; let i = 0; for (;;) { const l = 2 * i + 1, r = l + 1; let small = i; if (l < a.length && a[l] < a[small]) small = l; if (r < a.length && a[r] < a[small]) small = r; if (small === i) break; [a[small], a[i]] = [a[i], a[small]]; i = small; } } return top; }} const after = Array.from({ length: n + 1 }, () => []); // after[a] = a를 끝내야 할 수 있는 일들const waiting = new Array(n + 1).fill(0); // 먼저 끝내야 하는데 아직 안 끝난 일의 수for (let i = 0; i < m; i++) { const a = data[2 + 2 * i], b = data[3 + 2 * i]; after[a].push(b); waiting[b]++;} const ready = new MinHeap(); // 지금 할 수 있는 일들. 늘 가장 작은 번호를 꺼낸다for (let t = 1; t <= n; t++) if (waiting[t] === 0) ready.push(t);const order = [];while (ready.size > 0) { const t = ready.pop(); order.push(t); for (const next of after[t]) { if (--waiting[next] === 0) ready.push(next); }}// 고리(순환)가 있으면 그 안의 일은 waiting이 0이 되지 않아 끝까지 남는다console.log(order.length === n ? order.join(" ") : "-1");import { readFileSync } from "node:fs"; const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, m] = data; // 최소 힙: heap[0]이 가장 작고, i의 자식은 2i+1, 2i+2class MinHeap { private items: number[] = []; get size(): number { return this.items.length; } push(x: number): void { const a = this.items; a.push(x); let i = a.length - 1; while (i > 0) { const parent = (i - 1) >> 1; if (a[parent] <= a[i]) break; [a[parent], a[i]] = [a[i], a[parent]]; i = parent; } } pop(): number { const a = this.items; const top = a[0]; const last = a.pop()!; // size > 0일 때만 부른다 if (a.length > 0) { a[0] = last; let i = 0; for (;;) { const l = 2 * i + 1, r = l + 1; let small = i; if (l < a.length && a[l] < a[small]) small = l; if (r < a.length && a[r] < a[small]) small = r; if (small === i) break; [a[small], a[i]] = [a[i], a[small]]; i = small; } } return top; }} const after: number[][] = Array.from({ length: n + 1 }, (): number[] => []); // after[a] = a를 끝내야 할 수 있는 일들const waiting: number[] = new Array<number>(n + 1).fill(0); // 먼저 끝내야 하는데 아직 안 끝난 일의 수for (let i = 0; i < m; i++) { const a = data[2 + 2 * i], b = data[3 + 2 * i]; after[a].push(b); waiting[b]++;} const ready = new MinHeap(); // 지금 할 수 있는 일들. 늘 가장 작은 번호를 꺼낸다for (let t = 1; t <= n; t++) if (waiting[t] === 0) ready.push(t);const order: number[] = [];while (ready.size > 0) { const t = ready.pop(); order.push(t); for (const next of after[t]) { if (--waiting[next] === 0) ready.push(next); }}// 고리(순환)가 있으면 그 안의 일은 waiting이 0이 되지 않아 끝까지 남는다console.log(order.length === n ? order.join(" ") : "-1");import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.List;import java.util.PriorityQueue;import java.util.StringTokenizer; public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); int n = Integer.parseInt(st.nextToken()); int m = Integer.parseInt(st.nextToken()); List<List<Integer>> after = new ArrayList<>(); // after.get(a) = a를 끝내야 할 수 있는 일들 for (int t = 0; t <= n; t++) after.add(new ArrayList<>()); int[] waiting = new int[n + 1]; // 먼저 끝내야 하는데 아직 안 끝난 일의 수 for (int i = 0; i < m; i++) { st = new StringTokenizer(in.readLine()); int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); after.get(a).add(b); waiting[b]++; } // PriorityQueue는 기본이 최소 힙: poll()이 늘 가장 작은 번호를 꺼낸다 PriorityQueue<Integer> ready = new PriorityQueue<>(); for (int t = 1; t <= n; t++) if (waiting[t] == 0) ready.add(t); StringBuilder out = new StringBuilder(); int done = 0; while (!ready.isEmpty()) { int t = ready.poll(); if (done++ > 0) out.append(' '); out.append(t); for (int next : after.get(t)) { if (--waiting[next] == 0) ready.add(next); } } // 고리(순환)가 있으면 그 안의 일은 waiting이 0이 되지 않아 끝까지 남는다 System.out.println(done == n ? out.toString() : "-1"); }}using System;using System.Collections.Generic; class Program{ static void Main() { string[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(first[0]); int m = int.Parse(first[1]); var after = new List<int>[n + 1]; // after[a] = a를 끝내야 할 수 있는 일들 for (int t = 0; t <= n; t++) after[t] = new List<int>(); var waiting = new int[n + 1]; // 먼저 끝내야 하는데 아직 안 끝난 일의 수 for (int i = 0; i < m; i++) { string[] pair = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int a = int.Parse(pair[0]); int b = int.Parse(pair[1]); after[a].Add(b); waiting[b]++; } // PriorityQueue<값, 우선순위>: 우선순위가 작은 것부터 나온다. 번호를 우선순위로도 쓴다 var ready = new PriorityQueue<int, int>(); for (int t = 1; t <= n; t++) if (waiting[t] == 0) ready.Enqueue(t, t); var order = new List<int>(); while (ready.Count > 0) { int t = ready.Dequeue(); order.Add(t); foreach (int next in after[t]) { if (--waiting[next] == 0) ready.Enqueue(next, next); } } // 고리(순환)가 있으면 그 안의 일은 waiting이 0이 되지 않아 끝까지 남는다 Console.WriteLine(order.Count == n ? string.Join(" ", order) : "-1"); }}#include <functional>#include <iostream>#include <queue>#include <vector> int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, m; std::cin >> n >> m; std::vector<std::vector<int>> after(n + 1); // after[a] = a를 끝내야 할 수 있는 일들 std::vector<int> waiting(n + 1, 0); // 먼저 끝내야 하는데 아직 안 끝난 일의 수 for (int i = 0; i < m; i++) { int a, b; std::cin >> a >> b; after[a].push_back(b); waiting[b]++; } // std::priority_queue는 기본이 최대 힙이라 std::greater를 줘서 가장 작은 것이 위로 오게 한다 std::priority_queue<int, std::vector<int>, std::greater<int>> ready; for (int t = 1; t <= n; t++) if (waiting[t] == 0) ready.push(t); std::vector<int> order; while (!ready.empty()) { int t = ready.top(); ready.pop(); order.push_back(t); for (int next : after[t]) if (--waiting[next] == 0) ready.push(next); } // 고리(순환)가 있으면 그 안의 일은 waiting이 0이 되지 않아 끝까지 남는다 if (static_cast<int>(order.size()) < n) { std::cout << -1 << "\n"; } else { for (int i = 0; i < n; i++) std::cout << (i ? " " : "") << order[i]; std::cout << "\n"; }}#include <stdio.h> #define MAXN 10001#define MAXM 10000 /* 인접 목록을 배열로: head[a]는 a 뒤에 할 수 있는 첫 일 칸, next[e]는 다음 칸(-1이면 끝) */static int head[MAXN], next[MAXM], to[MAXM];static int waiting[MAXN]; /* 먼저 끝내야 하는데 아직 안 끝난 일의 수 */static int heap[MAXN], heap_size = 0; /* 최소 힙: heap[0]이 가장 작다 */static int order[MAXN]; static void swap(int* x, int* y) { int t = *x; *x = *y; *y = t;} static void heap_push(int x) { int i = heap_size++; heap[i] = x; while (i > 0 && heap[(i - 1) / 2] > heap[i]) { swap(&heap[(i - 1) / 2], &heap[i]); i = (i - 1) / 2; }} static int heap_pop(void) { int top = heap[0]; heap[0] = heap[--heap_size]; int i = 0; for (;;) { int l = 2 * i + 1, r = l + 1, small = i; if (l < heap_size && heap[l] < heap[small]) small = l; if (r < heap_size && heap[r] < heap[small]) small = r; if (small == i) break; swap(&heap[small], &heap[i]); i = small; } return top;} int main(void) { int n, m; scanf("%d %d", &n, &m); for (int t = 1; t <= n; t++) head[t] = -1; for (int e = 0; e < m; e++) { int a, b; scanf("%d %d", &a, &b); to[e] = b; next[e] = head[a]; head[a] = e; waiting[b]++; } for (int t = 1; t <= n; t++) if (waiting[t] == 0) heap_push(t); int done = 0; while (heap_size > 0) { int t = heap_pop(); /* 지금 할 수 있는 일 가운데 가장 작은 번호 */ order[done++] = t; for (int e = head[t]; e != -1; e = next[e]) if (--waiting[to[e]] == 0) heap_push(to[e]); } /* 고리(순환)가 있으면 그 안의 일은 waiting이 0이 되지 않아 끝까지 남는다 */ if (done < n) { puts("-1"); } else { for (int i = 0; i < n; i++) printf(i ? " %d" : "%d", order[i]); putchar('\n'); } return 0;}// 최소 힙(목록 heap): heap[0]이 가장 작고, i의 자식은 2i+1, 2i+2힙넣기(heap, x){ heap.넣기(x); i = heap.개수 - 1; 동안 (i > 0) { 부모 = 수학.몫(i - 1, 2); 만약 (heap[부모] <= heap[i]) { 그만; } t = heap[부모]; heap[부모] = heap[i]; heap[i] = t; i = 부모; }} 힙꺼내기(heap){ top = heap[0]; heap[0] = heap[heap.개수 - 1]; heap.자리빼기(heap.개수 - 1); i = 0; 동안 (참) { l = 2 * i + 1; r = l + 1; small = i; 만약 (l < heap.개수 && heap[l] < heap[small]) { small = l; } 만약 (r < heap.개수 && heap[r] < heap[small]) { small = r; } 만약 (small == i) { 그만; } t = heap[small]; heap[small] = heap[i]; heap[i] = t; i = small; } 돌려주기 top;} 첫줄 = 콘솔.수들읽기();n = 첫줄[0];m = 첫줄[1]; // 목록은 10,000칸까지라 일 번호에서 1을 빼 0번부터 둔다after = []; // after[a] = a를 끝내야 할 수 있는 일들반복 (t = 0; t < n; t++){ after.넣기([]);}waiting = 새목록(n, 0); // 먼저 끝내야 하는데 아직 안 끝난 일의 수반복 (i = 0; i < m; i++){ 쌍 = 콘솔.수들읽기(); after[쌍[0] - 1].넣기(쌍[1] - 1); waiting[쌍[1] - 1] += 1;} ready = []; // 지금 할 수 있는 일들(최소 힙). 늘 가장 작은 번호를 꺼낸다반복 (t = 0; t < n; t++){ 만약 (waiting[t] == 0) { 힙넣기(ready, t); }}order = [];동안 (ready.개수 > 0){ t = 힙꺼내기(ready); order.넣기(t + 1); 각각 (next 에서 after[t]) { waiting[next] -= 1; 만약 (waiting[next] == 0) { 힙넣기(ready, next); } }} // 고리(순환)가 있으면 그 안의 일은 waiting이 0이 되지 않아 끝까지 남는다만약 (order.개수 == n){ 콘솔.쓰기(order);}아니면{ 콘솔.쓰기(-1);}