위상 정렬P0381

단서만으로 정해지는 등수

달리기 대회에 1번부터 n번까지 선수 n명이 나갔고, 같은 등수는 없다. 단서 m개가 주어지며, 단서 "a b"는 a번 선수가 b번 선수보다 먼저 들어왔다는 뜻이다. 같은 단서가 여러 번 주어질 수 있고, 단서끼리 서로 어긋날 수도 있다. 단서만 보고 1등부터 차례로 등수를 정해 나간다. 아직 등수가 정해지지 않은 선수 가운데, 자기보다 먼저 들어왔다고 적힌 선수가 모두 이미 등수가 정해진 선수를 후보라고 한다. 자기보다 먼저 들어왔다는 단서가 하나도 없는 선수도 후보이다. 후보가 정확히 한 명이면 그 선수가 다음 등수가 되고, 남은 선수로 같은 일을 되풀이한다. 후보가 없거나 두 명 이상이면 거기서 멈춘다.
모든 선수의 등수가 정해져도 멈춘다. 첫째 줄에 등수가 정해진 선수의 번호를 1등부터 차례로 출력하라. 둘째 줄에 멈췄을 때의 후보 번호를 작은 것부터 차례로 출력하라.

입력: 첫 줄에 n과 m이 빈칸 하나로 나뉘어 주어진다.
다음 m줄에 줄마다 a와 b가 빈칸 하나로 나뉘어 주어진다.
1 ≤ n ≤ 50, 0 ≤ m ≤ 200, 1 ≤ a, b ≤ n, a ≠ b
출력: 두 줄.
번호는 빈칸 하나로 띄워 쓴다.
등수가 정해진 선수가 없으면 첫째 줄에 -만, 멈췄을 때 후보가 없으면 둘째 줄에 -만 출력한다

예시 1 · stdin

stdout

3 1 4
2 5

예시 2 · stdin

stdout

1
-

main.py 프로그래밍 언어 실행 판

입력(stdin)

실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).

$ 준비됐어요

코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.

다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이

후보를 찾아 하나씩 꺼내는 일이 곧 위상 정렬(칸 알고리즘)이에요.
선수마다 '자기보다 앞선다는 단서 가운데 그 앞 선수의 등수가 아직 안 정해진 것의 수'(waiting)를 세어 두면 waiting이 0인 선수가 후보예요.
후보의 등수를 정하면 그 선수보다 뒤라고 적힌 선수들의 waiting을 1씩 줄여요.
보통의 위상 정렬은 후보가 여럿이면 아무나 골라 끝까지 가지만, 이 문제는 후보가 정확히 하나일 때만 나아가요.
선수가 50명뿐이라 큐 없이 매번 모든 선수를 훑어도 충분해요.
선수마다 '뒤 선수 목록'을 두는 법이 언어마다 달라요.
Python [[] for _ in range(n + 1)], JavaScript·TypeScript Array.from({ length: n + 1 }, () => []), Java는 new ArrayList<>()를 n+1번 add하고, C#은 new List<int>[n + 1]을 만든 뒤 칸마다 new List<int>()를 넣어요.
C++ vector<vector<int>> after(n + 1)은 처음부터 칸마다 따로 있는 빈 vector예요.
C는 목록이 없어서 단서를 배열 둘(from, to)에 그대로 적어 두고 매번 훑어요.
크레이콘은 after.넣기([])를 n+1번 해요.
함정 하나: Python [[]] * (n + 1)과 JavaScript new Array(n + 1).fill([])은 목록 하나를 모든 칸이 함께 가리켜요.
첫째 예시에서 3번의 등수를 정할 때 모든 단서의 뒤 선수가 한꺼번에 줄어서 3과 1 2 4 5가 나와요.
함정 둘: C#에서 칸마다 new를 빠뜨리면 칸이 null이라 첫 Add에서 NullReferenceException으로 멈춰요.
함정 셋: 같은 단서가 두 번 나올 때 뒤 선수는 집합(set)으로 한 번만 잇고 waiting은 줄마다 세면 안 돼요.
첫째 예시의 1번은 waiting이 2에서 1까지만 줄어서 3과 -가 나와요.
둘 다 나온 만큼 넣고 세요.
함정 넷: 후보가 여럿일 때 가장 작은 번호를 골라 계속 가면(보통의 위상 정렬) 첫째 예시에서 3 1 4 2 5와 -가 나와요.
2번과 5번 가운데 누가 먼저인지는 단서로 알 수 없어요.
함정 다섯: 등수가 정해진 선수를 표시해 두지 않으면 그 선수의 waiting이 0인 채로 남아 다음에도 후보로 세어져요.
첫째 예시에서 3과 1 3이 나와요.
함정 여섯: 빈 목록을 쓰는 법이에요.
Python " ".join([])과 JavaScript [].join(" ")은 빈 문자열이라 - 대신 빈 줄이 나와요(둘째 예시의 둘째 줄).
수 목록을 잇는 법도 달라요.
Python은 map(str, order)로 문자열로 바꿔야 join이 되고, JavaScript join과 C# string.Join은 수를 그대로 받아요.
Java String.join은 문자열만 받아서 StringBuilder로 잇고, C·C++은 반복문으로 써요.
크레이콘은 콘솔.쓰기(order)처럼 목록을 쓰면 빈칸으로 이어 써요.

Pythonmain.py · 26 줄

import 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)             # 아직 등수가 안 정해진 '앞선 선수' 단서의 수for i in range(m):    a, b = int(data[2 + 2 * i]), int(data[3 + 2 * i])    after[a].append(b)  # 같은 단서가 또 나오면 또 넣고    waiting[b] += 1     # 또 센다(둘이 늘 맞는다) placed = [False] * (n + 1)order = []while True:    cand = [v for v in range(1, n + 1) if not placed[v] and waiting[v] == 0]    if len(cand) != 1:  # 후보가 없거나 여럿이면 멈춘다        break    v = cand[0]    placed[v] = True    order.append(v)    for b in after[v]:        waiting[b] -= 1 # " ".join([])은 빈 문자열이라 빈 목록은 따로 "-"로 쓴다print(" ".join(map(str, order)) if order else "-")print(" ".join(map(str, cand)) if cand else "-")

JavaScriptmain.js · 26 줄

const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, m] = data;// fill([])은 같은 배열 하나를 모든 칸에 넣으니 칸마다 새 배열을 만든다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 placed = new Array(n + 1).fill(false);const order = [];let cand = [];while (true) {  cand = [];  for (let v = 1; v <= n; v++) if (!placed[v] && waiting[v] === 0) cand.push(v);  if (cand.length !== 1) break; // 후보가 없거나 여럿이면 멈춘다  const v = cand[0];  placed[v] = true;  order.push(v);  for (const b of after[v]) waiting[b]--;} console.log(order.length ? order.join(" ") : "-");console.log(cand.length ? cand.join(" ") : "-");

TypeScriptmain.ts · 26 줄

const data: number[] = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, m] = data;// fill([])은 같은 배열 하나를 모든 칸에 넣으니 칸마다 새 배열을 만든다const after: number[][] = Array.from({ length: n + 1 }, () => []); // after[a] = a보다 늦게 들어왔다고 적힌 선수들const waiting: number[] = 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 placed: boolean[] = new Array(n + 1).fill(false);const order: number[] = [];let cand: number[] = [];while (true) {  cand = [];  for (let v = 1; v <= n; v++) if (!placed[v] && waiting[v] === 0) cand.push(v);  if (cand.length !== 1) break; // 후보가 없거나 여럿이면 멈춘다  const v = cand[0];  placed[v] = true;  order.push(v);  for (const b of after[v]) waiting[b]--;} console.log(order.length ? order.join(" ") : "-");console.log(cand.length ? cand.join(" ") : "-");

JavaMain.java · 43 줄

import java.util.*; public class Main {    // 수 목록을 빈칸으로 이어 쓴다(비었으면 "-")    static String show(List<Integer> list) {        if (list.isEmpty()) return "-";        StringBuilder sb = new StringBuilder();        for (int v : list) {            if (sb.length() > 0) sb.append(' ');            sb.append(v);        }        return sb.toString();    }     public static void main(String[] args) {        Scanner in = new Scanner(System.in);        int n = in.nextInt(), m = in.nextInt();        List<List<Integer>> after = new ArrayList<>(); // after.get(a) = a보다 늦게 들어왔다고 적힌 선수들        for (int v = 0; v <= n; v++) after.add(new ArrayList<>());        int[] waiting = new int[n + 1]; // 아직 등수가 안 정해진 '앞선 선수' 단서의 수        for (int i = 0; i < m; i++) {            int a = in.nextInt(), b = in.nextInt();            after.get(a).add(b);            waiting[b]++;        }         boolean[] placed = new boolean[n + 1];        List<Integer> order = new ArrayList<>();        List<Integer> cand;        while (true) {            cand = new ArrayList<>();            for (int v = 1; v <= n; v++) if (!placed[v] && waiting[v] == 0) cand.add(v);            if (cand.size() != 1) break; // 후보가 없거나 여럿이면 멈춘다            int v = cand.get(0);            placed[v] = true;            order.add(v);            for (int b : after.get(v)) waiting[b]--;        }         System.out.println(show(order));        System.out.println(show(cand));    }}

C#Main.cs · 38 줄

using System;using System.Collections.Generic; class Program{    static void Main()    {        var data = Console.In.ReadToEnd().Split((char[]?)null, StringSplitOptions.RemoveEmptyEntries);        int n = int.Parse(data[0]), m = int.Parse(data[1]);        var after = new List<int>[n + 1]; // after[a] = a보다 늦게 들어왔다고 적힌 선수들        for (int v = 0; v <= n; v++) after[v] = new List<int>(); // 칸마다 new를 해야 한다(처음에는 null)        var waiting = new int[n + 1]; // 아직 등수가 안 정해진 '앞선 선수' 단서의 수        for (int i = 0; i < m; i++)        {            int a = int.Parse(data[2 + 2 * i]), b = int.Parse(data[3 + 2 * i]);            after[a].Add(b);            waiting[b]++;        }         var placed = new bool[n + 1];        var order = new List<int>();        List<int> cand;        while (true)        {            cand = new List<int>();            for (int v = 1; v <= n; v++) if (!placed[v] && waiting[v] == 0) cand.Add(v);            if (cand.Count != 1) break; // 후보가 없거나 여럿이면 멈춘다            int w = cand[0];            placed[w] = true;            order.Add(w);            foreach (int b in after[w]) waiting[b]--;        }         // string.Join은 수 목록도 바로 이어 준다        Console.WriteLine(order.Count > 0 ? string.Join(" ", order) : "-");        Console.WriteLine(cand.Count > 0 ? string.Join(" ", cand) : "-");    }}

C++main.cpp · 43 줄

#include <iostream>#include <vector>using namespace std; // 수 목록을 빈칸으로 이어 쓴다(비었으면 "-")void show(const vector<int>& list) {    if (list.empty()) cout << "-";    for (size_t i = 0; i < list.size(); i++) {        if (i > 0) cout << ' ';        cout << list[i];    }    cout << '\n';} int main() {    int n, m;    cin >> n >> m;    vector<vector<int>> after(n + 1); // after[a] = a보다 늦게 들어왔다고 적힌 선수들(칸마다 따로 있는 빈 vector)    vector<int> waiting(n + 1, 0);    // 아직 등수가 안 정해진 '앞선 선수' 단서의 수    for (int i = 0; i < m; i++) {        int a, b;        cin >> a >> b;        after[a].push_back(b);        waiting[b]++;    }     vector<bool> placed(n + 1, false);    vector<int> order, cand;    while (true) {        cand.clear();        for (int v = 1; v <= n; v++)            if (!placed[v] && waiting[v] == 0) cand.push_back(v);        if (cand.size() != 1) break; // 후보가 없거나 여럿이면 멈춘다        int v = cand[0];        placed[v] = true;        order.push_back(v);        for (int b : after[v]) waiting[b]--;    }     show(order);    show(cand);    return 0;}

Cmain.c · 41 줄

#include <stdio.h> #define MAXN 50#define MAXM 200 // 수 k개를 빈칸으로 이어 쓴다(없으면 "-")void show(const int *a, int k) {    if (k == 0) printf("-");    for (int i = 0; i < k; i++) printf(i ? " %d" : "%d", a[i]);    printf("\n");} int main(void) {    int n, m;    if (scanf("%d %d", &n, &m) != 2) return 0;    int from[MAXM], to[MAXM];       // 단서를 그대로 적어 둔다(같은 단서도 그대로)    int waiting[MAXN + 1] = {0};    // 아직 등수가 안 정해진 '앞선 선수' 단서의 수    for (int i = 0; i < m; i++) {        scanf("%d %d", &from[i], &to[i]);        waiting[to[i]]++;    }     int placed[MAXN + 1] = {0};    int order[MAXN], cand[MAXN];    int count = 0, k = 0;    while (1) {        k = 0;        for (int v = 1; v <= n; v++)            if (!placed[v] && waiting[v] == 0) cand[k++] = v;        if (k != 1) break; // 후보가 없거나 여럿이면 멈춘다        int v = cand[0];        placed[v] = 1;        order[count++] = v;        for (int i = 0; i < m; i++)            if (from[i] == v) waiting[to[i]]--;    }     show(order, count);    show(cand, k);    return 0;}

Craykonmain.cray · 57 줄

// 수 목록을 빈칸으로 이어 쓴다(비었으면 "-")보여주기(list){    만약 (list.개수 == 0)    {        콘솔.쓰기("-");    }    아니면    {        콘솔.쓰기(list); // 목록을 쓰면 빈칸으로 이어 쓴다    }} 첫줄 = 콘솔.수들읽기();n = 첫줄[0];m = 첫줄[1];after = []; // after[a] = a보다 늦게 들어왔다고 적힌 선수들반복 (v = 0; v <= n; v++){    after.넣기([]); // 칸마다 새 목록을 만든다}waiting = 새목록(n + 1, 0); // 아직 등수가 안 정해진 '앞선 선수' 단서의 수반복 (i = 0; i < m; i++){    쌍 = 콘솔.수들읽기();    after[쌍[0]].넣기(쌍[1]);    waiting[쌍[1]] += 1;} placed = 새목록(n + 1, 거짓);order = [];cand = [];동안 (참){    cand = [];    반복 (v = 1; v <= n; v++)    {        만약 (!placed[v] && waiting[v] == 0)        {            cand.넣기(v);        }    }    만약 (cand.개수 != 1)    {        그만; // 후보가 없거나 여럿이면 멈춘다    }    w = cand[0];    placed[w] = 참;    order.넣기(w);    각각 (b 에서 after[w])    {        waiting[b] -= 1;    }} 보여주기(order);보여주기(cand);