단체 대화방에 1번부터 n번까지 n명이 있다.
사람마다 방 안의 다른 사람 몇 명을 지켜본다. "a b"는 a가 b를 지켜본다는 뜻이고, b가 a를 지켜보는지와는 상관없다.
i번 사람에게는 기준 tᵢ가 있다.
날마다 그날 아침에 방에 있는 사람마다, 자기가 지켜보는 사람 가운데 아직 방에 있는 사람의 수를 센다.
그 수가 기준 tᵢ보다 작은 사람은 모두 그날 함께 방을 나간다.
같은 날 나가는 사람들은 서로를 보고 나가는 것이 아니다. 그날 아침에 센 수로만 정한다.
나간 사람은 다시 들어오지 않는다.
첫날 아침에는 모두 방에 있고, 아무도 나가지 않는 날이 오면 그 뒤로도 아무도 나가지 않는다.
첫 줄에 끝까지 남는 사람의 수를 출력하라.
둘째 줄에 1번부터 n번까지 사람마다 방을 나간 날(첫날이 1)을 출력하고, 끝까지 남는 사람은 0을 출력하라.
입력
첫 줄에 n과 지켜보기 관계의 수 m, 둘째 줄에 t₁ … tₙ, 다음 m줄에 "a b"가 빈칸 하나로 나뉘어 주어진다. 1 ≤ n ≤ 10,000, 0 ≤ m ≤ 30,000, 0 ≤ tᵢ ≤ 10,000. 1 ≤ a, b ≤ n이고 a ≠ b이며, 같은 "a b"는 두 번 나오지 않는다("a b"와 "b a"는 함께 나올 수 있다)
출력
두 줄: 남는 사람의 수, 그리고 사람마다 나간 날 n개(빈칸 하나로 나눈다)
예시 1 · stdin
6 6
1 2 1 0 1 2
1 2
2 1
2 3
3 5
6 4
6 1
stdout
1
4 3 2 0 1 5
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
날마다 모두를 다시 세면 하루에 m번, 날은 n일까지 가서(한 줄로 이어 지켜보면 10,000일) 3억 번이라 느려요. 바뀌는 사람만 봐요: watching[v] = v가 지켜보는 사람 가운데 남은 수를 들고, 오늘 나간 u마다 u를 지켜보던 사람들의 수만 1씩 줄여요. 그러려면 "a b"를 followers[b]에 a를 넣어 거꾸로 저장해야 해요 — a의 목록에 b를 넣으면 u가 지켜보던 사람의 수를 줄이게 돼 틀려요. 수가 기준 밑으로 처음 내려간 사람은 그 순간 '다음 날 나감'으로 적고 내일 목록에 넣어요(오늘 나간 사람이 다 빠진 뒤에 세는 것과 같아요). 한 사람은 한 번만 넣어야 해서, 이미 나갔거나 나가기로 정해진 사람(day[w] != 0)은 건드리지 않아요 — 이 확인이 없으면 같은 사람이 목록에 두 번 들어가 그 사람을 지켜보던 사람들의 수가 두 번 줄어요. 날마다 목록을 따로 두거나(오늘·내일), 큐 하나에 넣고 day[w] = day[u] + 1로 적어도 돼요(너비 우선 탐색과 같은 모양). 예시: 5번(지켜보는 사람 없음, 기준 1)이 첫날, 5번을 지켜보던 3번이 둘째 날, 그다음 2번·1번·6번이 하루씩 늦게 나가고, 기준이 0인 4번만 남아요. 함정 하나: 날마다 1번부터 차례로 보며 그 자리에서 바로 내보내면, 같은 날 앞 번호가 나간 것을 뒤 번호가 그날 바로 느껴 날이 앞당겨져요. 함정 둘: 기준과 같으면 남아요(<, <=가 아니에요). 인접 목록은 언어마다 달라요: Python [[] for _ in range(n)]([[]] * n은 한 목록을 n번 가리켜요), JavaScript·TypeScript Array.from({ length: n }, () => [])(new Array(n).fill([])도 한 목록을 함께 써요), Java List<List<Integer>>, C# List<int>[], C++ std::vector<std::vector<int>>, C는 크기가 정해진 배열 두 개로 '시작 자리 + 이어 붙인 목록'(CSR)을 만들어요. 크레이콘은 목록의 목록을 followers.넣기([])로 n번 만들어요 — 목록은 10,000칸까지라 n도 10,000까지예요.
Pythonmain.py · 33 줄
import sysdata = sys.stdin.buffer.read().split()n, m = int(data[0]), int(data[1])need = [int(x) for x in data[2:2 + n]]followers = [[] for _ in range(n)] # followers[b] = b를 지켜보는 사람들(화살표를 거꾸로 저장)watching = [0] * n # 지켜보는 사람 가운데 아직 방에 있는 수pos = 2 + nfor _ in range(m): a, b = int(data[pos]) - 1, int(data[pos + 1]) - 1 pos += 2 followers[b].append(a) watching[a] += 1day = [0] * n # 나간 날(0은 끝까지 남음)today = [v for v in range(n) if watching[v] < need[v]]for v in today: day[v] = 1d = 1while today: tomorrow = [] for u in today: # 오늘 나간 사람 u를 지켜보던 사람들의 수가 준다 for w in followers[u]: if day[w] == 0: # 이미 나갔거나 나가기로 정해진 사람은 건드리지 않는다 watching[w] -= 1 if watching[w] < need[w]: day[w] = d + 1 # 오늘 나간 사람들이 모두 빠진 뒤에 세니, 다음 날 나간다 tomorrow.append(w) today = tomorrow d += 1print(day.count(0))print(" ".join(map(str, day)))
JavaScriptmain.js · 36 줄
const data = require("fs").readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, m] = data;const need = data.slice(2, 2 + n);const followers = Array.from({ length: n }, () => []); // followers[b] = b를 지켜보는 사람들(화살표를 거꾸로 저장)const watching = new Array(n).fill(0); // 지켜보는 사람 가운데 아직 방에 있는 수for (let i = 0; i < m; i++) { const a = data[2 + n + 2 * i] - 1; const b = data[3 + n + 2 * i] - 1; followers[b].push(a); watching[a]++;}const day = new Array(n).fill(0); // 나간 날(0은 끝까지 남음)let today = [];for (let v = 0; v < n; v++) { if (watching[v] < need[v]) { day[v] = 1; today.push(v); }}for (let d = 1; today.length > 0; d++) { const tomorrow = []; for (const u of today) { // 오늘 나간 사람 u를 지켜보던 사람들의 수가 준다 for (const w of followers[u]) { if (day[w] !== 0) continue; // 이미 나갔거나 나가기로 정해진 사람은 건드리지 않는다 watching[w]--; if (watching[w] < need[w]) { day[w] = d + 1; // 오늘 나간 사람들이 모두 빠진 뒤에 세니, 다음 날 나간다 tomorrow.push(w); } } } today = tomorrow;}console.log(day.filter((x) => x === 0).length + "\n" + day.join(" "));
TypeScriptmain.ts · 38 줄
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").trim().split(/\s+/).map(Number);const [n, m] = data;const need: number[] = data.slice(2, 2 + n);const followers: number[][] = Array.from({ length: n }, () => []); // followers[b] = b를 지켜보는 사람들(화살표를 거꾸로 저장)const watching: number[] = new Array<number>(n).fill(0); // 지켜보는 사람 가운데 아직 방에 있는 수for (let i = 0; i < m; i++) { const a = data[2 + n + 2 * i] - 1; const b = data[3 + n + 2 * i] - 1; followers[b].push(a); watching[a]++;}const day: number[] = new Array<number>(n).fill(0); // 나간 날(0은 끝까지 남음)let today: number[] = [];for (let v = 0; v < n; v++) { if (watching[v] < need[v]) { day[v] = 1; today.push(v); }}for (let d = 1; today.length > 0; d++) { const tomorrow: number[] = []; for (const u of today) { // 오늘 나간 사람 u를 지켜보던 사람들의 수가 준다 for (const w of followers[u]) { if (day[w] !== 0) continue; // 이미 나갔거나 나가기로 정해진 사람은 건드리지 않는다 watching[w]--; if (watching[w] < need[w]) { day[w] = d + 1; // 오늘 나간 사람들이 모두 빠진 뒤에 세니, 다음 날 나간다 tomorrow.push(w); } } } today = tomorrow;}console.log(day.filter((x) => x === 0).length + "\n" + day.join(" "));
JavaMain.java · 58 줄
import java.io.*;import java.util.*;public class Main { public static void main(String[] args) throws IOException { StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); st.nextToken(); int n = (int) st.nval; st.nextToken(); int m = (int) st.nval; int[] need = new int[n]; for (int v = 0; v < n; v++) { st.nextToken(); need[v] = (int) st.nval; } // followers.get(b) = b를 지켜보는 사람들(화살표를 거꾸로 저장) List<List<Integer>> followers = new ArrayList<>(); for (int v = 0; v < n; v++) followers.add(new ArrayList<>()); int[] watching = new int[n]; // 지켜보는 사람 가운데 아직 방에 있는 수 for (int i = 0; i < m; i++) { st.nextToken(); int a = (int) st.nval - 1; st.nextToken(); int b = (int) st.nval - 1; followers.get(b).add(a); watching[a]++; } int[] day = new int[n]; // 나간 날(0은 끝까지 남음) List<Integer> today = new ArrayList<>(); for (int v = 0; v < n; v++) { if (watching[v] < need[v]) { day[v] = 1; today.add(v); } } for (int d = 1; !today.isEmpty(); d++) { List<Integer> tomorrow = new ArrayList<>(); for (int u : today) { // 오늘 나간 사람 u를 지켜보던 사람들의 수가 준다 for (int w : followers.get(u)) { if (day[w] != 0) continue; // 이미 나갔거나 나가기로 정해진 사람은 건드리지 않는다 if (--watching[w] < need[w]) { day[w] = d + 1; // 오늘 나간 사람들이 모두 빠진 뒤에 세니, 다음 날 나간다 tomorrow.add(w); } } } today = tomorrow; } int stay = 0; StringBuilder sb = new StringBuilder(); for (int v = 0; v < n; v++) { if (day[v] == 0) stay++; sb.append(day[v]).append(v + 1 < n ? ' ' : '\n'); } System.out.print(stay + "\n" + sb); }}
C#Main.cs · 51 줄
using System;using System.Collections.Generic;using System.Linq;class Program{ static void Main() { var data = Console.In.ReadToEnd().Split((char[]?)null, StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray(); int n = data[0], m = data[1]; int[] need = data[2..(2 + n)]; var followers = new List<int>[n]; // followers[b] = b를 지켜보는 사람들(화살표를 거꾸로 저장) for (int v = 0; v < n; v++) followers[v] = new List<int>(); var watching = new int[n]; // 지켜보는 사람 가운데 아직 방에 있는 수 for (int i = 0; i < m; i++) { int a = data[2 + n + 2 * i] - 1, b = data[3 + n + 2 * i] - 1; followers[b].Add(a); watching[a]++; } var day = new int[n]; // 나간 날(0은 끝까지 남음) var today = new List<int>(); for (int v = 0; v < n; v++) { if (watching[v] < need[v]) { day[v] = 1; today.Add(v); } } for (int d = 1; today.Count > 0; d++) { var tomorrow = new List<int>(); foreach (int u in today) // 오늘 나간 사람 u를 지켜보던 사람들의 수가 준다 { foreach (int w in followers[u]) { if (day[w] != 0) continue; // 이미 나갔거나 나가기로 정해진 사람은 건드리지 않는다 if (--watching[w] < need[w]) { day[w] = d + 1; // 오늘 나간 사람들이 모두 빠진 뒤에 세니, 다음 날 나간다 tomorrow.Add(w); } } } today = tomorrow; } Console.Write(day.Count(x => x == 0) + "\n" + string.Join(' ', day) + "\n"); }}
C++main.cpp · 41 줄
#include <iostream>#include <vector>int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, m; std::cin >> n >> m; std::vector<int> need(n); for (int &x : need) std::cin >> x; std::vector<std::vector<int>> followers(n); // followers[b] = b를 지켜보는 사람들(화살표를 거꾸로 저장) std::vector<int> watching(n, 0); // 지켜보는 사람 가운데 아직 방에 있는 수 for (int i = 0; i < m; i++) { int a, b; std::cin >> a >> b; followers[b - 1].push_back(a - 1); watching[a - 1]++; } std::vector<int> day(n, 0); // 나간 날(0은 끝까지 남음) std::vector<int> today; for (int v = 0; v < n; v++) if (watching[v] < need[v]) day[v] = 1, today.push_back(v); int left = 0; for (int d = 1; !today.empty(); d++) { left += static_cast<int>(today.size()); std::vector<int> tomorrow; for (int u : today) { // 오늘 나간 사람 u를 지켜보던 사람들의 수가 준다 for (int w : followers[u]) { if (day[w] != 0) continue; // 이미 나갔거나 나가기로 정해진 사람은 건드리지 않는다 if (--watching[w] < need[w]) { day[w] = d + 1; // 오늘 나간 사람들이 모두 빠진 뒤에 세니, 다음 날 나간다 tomorrow.push_back(w); } } } today.swap(tomorrow); } std::cout << n - left << '\n'; for (int v = 0; v < n; v++) std::cout << day[v] << (v + 1 < n ? ' ' : '\n');}
Cmain.c · 43 줄
#include <stdio.h>#include <stdlib.h>int main(void) { int n, m; if (scanf("%d %d", &n, &m) != 2) return 0; int *need = malloc(sizeof(int) * n); for (int v = 0; v < n; v++) scanf("%d", &need[v]); int *ea = malloc(sizeof(int) * (m + 1)), *eb = malloc(sizeof(int) * (m + 1)); int *watching = calloc(n, sizeof(int)); /* 지켜보는 사람 가운데 아직 방에 있는 수 */ int *start = calloc(n + 1, sizeof(int)); /* 거꾸로 된 인접 목록(CSR): b를 지켜보는 사람들이 who[start[b] .. start[b+1]) */ for (int i = 0; i < m; i++) { scanf("%d %d", &ea[i], &eb[i]); ea[i]--, eb[i]--; watching[ea[i]]++; start[eb[i] + 1]++; } for (int v = 0; v < n; v++) start[v + 1] += start[v]; int *fill = malloc(sizeof(int) * (n + 1)), *who = malloc(sizeof(int) * (m + 1)); for (int v = 0; v <= n; v++) fill[v] = start[v]; for (int i = 0; i < m; i++) who[fill[eb[i]]++] = ea[i]; int *day = calloc(n, sizeof(int)); /* 나간 날(0은 끝까지 남음) */ int *queue = malloc(sizeof(int) * n); /* 나간 차례: 날이 같은 사람끼리 이어져 있다 */ int head = 0, tail = 0; for (int v = 0; v < n; v++) if (watching[v] < need[v]) day[v] = 1, queue[tail++] = v; while (head < tail) { int u = queue[head++]; for (int j = start[u]; j < start[u + 1]; j++) { /* u를 지켜보던 사람들의 수가 준다 */ int w = who[j]; if (day[w] != 0) continue; /* 이미 나갔거나 나가기로 정해진 사람은 건드리지 않는다 */ if (--watching[w] < need[w]) { day[w] = day[u] + 1; /* u의 날에 나간 사람들이 모두 빠진 뒤에 세니, 다음 날 나간다 */ queue[tail++] = w; } } } printf("%d\n", n - tail); for (int v = 0; v < n; v++) printf("%d%c", day[v], v + 1 < n ? ' ' : '\n'); free(need), free(ea), free(eb), free(watching), free(start), free(fill), free(who), free(day), free(queue); return 0;}
Craykonmain.cray · 55 줄
첫줄 = 콘솔.수들읽기();n = 첫줄[0];m = 첫줄[1];need = 콘솔.수들읽기();followers = []; // followers[b] = b를 지켜보는 사람들(화살표를 거꾸로 저장). 번호에서 1을 빼 0번부터 둔다반복 (v = 0; v < n; v++){ followers.넣기([]);}watching = 새목록(n, 0); // 지켜보는 사람 가운데 아직 방에 있는 수반복 (i = 0; i < m; i++){ e = 콘솔.수들읽기(); a = e[0] - 1; b = e[1] - 1; followers[b].넣기(a); watching[a] += 1;}day = 새목록(n, 0); // 나간 날(0은 끝까지 남음)today = [];반복 (v = 0; v < n; v++){ 만약 (watching[v] < need[v]) { day[v] = 1; today.넣기(v); }}d = 1;남은수 = n;동안 (today.개수 > 0){ 남은수 -= today.개수; tomorrow = []; 각각 (u 에서 today) { 각각 (w 에서 followers[u]) { 만약 (day[w] == 0) { watching[w] -= 1; 만약 (watching[w] < need[w]) { day[w] = d + 1; // 오늘 나간 사람들이 모두 빠진 뒤에 세니, 다음 날 나간다 tomorrow.넣기(w); } } } } today = tomorrow; d += 1;}콘솔.쓰기(남은수);콘솔.쓰기(day);