파일이 n개 있고 1번부터 n번까지 번호가 있다.
i번 파일에는 마지막으로 고친 시각 t_i와, 그 파일을 만들 때 쓰는 재료 파일의 목록이 있다.
재료 목록에 아무것도 없는 파일은 사람이 직접 쓴 원본이며, 다시 만드는 일이 없다.
재료를 따라가서 제자리로 돌아오는 일은 없다.
목표 파일 g를 최신으로 만들려고 g를 '살핀다'. 파일 x를 살핀다는 것은 다음과 같다.
x를 이미 살폈으면 아무것도 하지 않는다.
아니면 먼저 x의 재료를 목록에 적힌 차례대로 하나씩 살핀다.
재료를 모두 살핀 뒤, 재료 가운데 이번에 다시 만든 파일이 하나라도 있거나 고친 시각이 t_x보다 큰 파일이 하나라도 있으면 x를 다시 만든다.
고친 시각이 t_x와 같은 재료는 x보다 새것이 아니다.
g를 살피는 동안 한 번도 살피지 않은 파일은 낡았더라도 다시 만들지 않는다.
예제에서 1번을 살피면 먼저 재료 3번을 살핀다. 3번은 재료 4번과 5번을 살핀 뒤, 5번(70)이 자기(60)보다 새것이므로 다시 만든다.
다음으로 2번을 살피는데, 재료 4번(30)이 2번(40)보다 오래됐으므로 그대로 둔다.
1번(80)은 어느 재료보다도 나중에 고쳤지만, 3번을 방금 다시 만들었으므로 1번도 다시 만든다.
6번은 재료 5번보다 오래됐지만 1번을 만드는 데 쓰이지 않으므로 그대로 둔다.
다시 만드는 파일을 다시 만드는 차례대로 구하라.
입력
첫 줄에 n과 g가 빈칸으로 나뉘어 주어진다. 둘째 줄에 t_1부터 t_n까지 빈칸 하나로 나뉘어 주어진다. 다음 n줄 가운데 i번째 줄에는 i번 파일의 재료 수 k와 재료 번호 k개가 빈칸 하나로 나뉘어 주어진다(재료가 없으면 0만 있다). 한 파일의 재료 목록에 같은 번호가 두 번 나오지 않는다. 1 ≤ n ≤ 5,000, 1 ≤ g ≤ n, 1 ≤ t_i ≤ 1,000,000,000, 모든 파일의 재료 수를 더하면 10,000 이하. g에서 재료를 따라 내려가는 어떤 길에도 파일이 g를 넣어 1,000개를 넘지 않는다
출력
첫 줄에 다시 만드는 파일의 수. 둘째 줄에 그 파일 번호를 다시 만드는 차례대로 빈칸 하나로 띄워 출력한다. 다시 만드는 파일이 없으면 첫 줄에 0만 출력하고 둘째 줄은 출력하지 않는다
예시 1 · stdin
6 1
80 40 60 30 70 10
2 3 2
1 4
2 4 5
0
0
1 5
stdout
2
3 1
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
재료를 모두 살핀 다음에야 자기를 적는 차례는 깊이 우선 탐색의 '나올 때 적기'(후위 순서)이고, 이것이 곧 위상 정렬이에요. 어떤 파일도 제 재료보다 먼저 나오지 않아요. 들어오는 선의 수를 세어 큐로 꺼내는 방법도 위상 정렬이지만, 여기서는 목표에 필요한 파일만 재료가 적힌 차례대로 만들어야 하므로 재귀가 맞아요. 재귀 깊이가 언어마다 달라요. Python은 기본 한도가 1,000이라 재료가 1,000단계 이어지면 RecursionError로 멈추니 sys.setrecursionlimit(10000)처럼 올려요. JS·TS·Java·C#·C·C++·크레이콘은 이 깊이에서 그대로 돌아요. 함수 안에서 바깥 표시 목록을 고치는 법도 달라요. Python은 안쪽 함수에서 바깥 목록의 칸을 바꾸는 것은 nonlocal 없이 되고, Java·C#은 static 필드, C는 전역 배열, JS·TS·C++은 바깥 변수를 그대로 써요. 크레이콘도 함수 안에서 looked[x] = 참;처럼 바깥 목록을 바로 고쳐요. 함정 하나: 시각이 같으면 새것이 아니에요. >=가 아니라 >예요. 함정 둘: 재료에 적힌 시각이 더 오래됐어도 그 재료를 이번에 다시 만들었다면 자기도 다시 만들어야 해요(예제의 1번). 그래서 '살폈다'와 '다시 만들었다' 표시를 따로 둬요. 함정 셋: 살핀 파일을 표시하지 않으면 두 파일이 함께 쓰는 재료를 두 번 만들어요. 함정 넷: 1번부터 n번까지 모두 살피면 목표에 필요 없는 낡은 파일(예제의 6번)까지 만들어요. 함정 다섯: 재료를 번호 차례로 정렬해서 살피거나, 고른 파일을 번호 차례로 출력하면 차례가 달라져요(예제의 답은 1 3이 아니라 3 1).
Pythonmain.py · 37 줄
import syssys.setrecursionlimit(10000) # 재료를 따라 1,000단계까지 내려간다(기본 한도는 1,000)def main(): data = sys.stdin.read().split() n, goal = int(data[0]), int(data[1]) t = [0] + [int(x) for x in data[2:2 + n]] deps = [[]] pos = 2 + n for _ in range(n): k = int(data[pos]) deps.append([int(x) for x in data[pos + 1:pos + 1 + k]]) pos += 1 + k looked = [False] * (n + 1) # 이미 살핀 파일 rebuilt = [False] * (n + 1) # 이번에 다시 만든 파일 order = [] # 다시 만든 차례 def look(x): looked[x] = True stale = False for a in deps[x]: # 재료를 적힌 차례대로 먼저 살핀다 if not looked[a]: look(a) if rebuilt[a] or t[a] > t[x]: stale = True if stale: # 재료를 모두 살핀 뒤에야 자기를 만든다 rebuilt[x] = True order.append(x) look(goal) print(len(order)) if order: print(" ".join(map(str, order)))main()
JavaScriptmain.js · 34 줄
const data = require("fs").readFileSync(0, "utf8").split(/\s+/).filter(Boolean).map(Number);const n = data[0];const goal = data[1];const t = [0, ...data.slice(2, 2 + n)];const deps = [[]];let pos = 2 + n;for (let i = 0; i < n; i++) { const k = data[pos]; deps.push(data.slice(pos + 1, pos + 1 + k)); pos += 1 + k;}const looked = new Array(n + 1).fill(false); // 이미 살핀 파일const rebuilt = new Array(n + 1).fill(false); // 이번에 다시 만든 파일const order = []; // 다시 만든 차례function look(x) { looked[x] = true; let stale = false; for (const a of deps[x]) { // 재료를 적힌 차례대로 먼저 살핀다 if (!looked[a]) look(a); if (rebuilt[a] || t[a] > t[x]) stale = true; } if (stale) { // 재료를 모두 살핀 뒤에야 자기를 만든다 rebuilt[x] = true; order.push(x); }}look(goal);console.log(order.length);if (order.length > 0) console.log(order.join(" "));
TypeScriptmain.ts · 35 줄
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").split(/\s+/).filter(Boolean).map(Number);const n: number = data[0];const goal: number = data[1];const t: number[] = [0, ...data.slice(2, 2 + n)];const deps: number[][] = [[]];let pos = 2 + n;for (let i = 0; i < n; i++) { const k = data[pos]; deps.push(data.slice(pos + 1, pos + 1 + k)); pos += 1 + k;}const looked: boolean[] = new Array<boolean>(n + 1).fill(false); // 이미 살핀 파일const rebuilt: boolean[] = new Array<boolean>(n + 1).fill(false); // 이번에 다시 만든 파일const order: number[] = []; // 다시 만든 차례function look(x: number): void { looked[x] = true; let stale = false; for (const a of deps[x]) { // 재료를 적힌 차례대로 먼저 살핀다 if (!looked[a]) look(a); if (rebuilt[a] || t[a] > t[x]) stale = true; } if (stale) { // 재료를 모두 살핀 뒤에야 자기를 만든다 rebuilt[x] = true; order.push(x); }}look(goal);console.log(order.length);if (order.length > 0) console.log(order.join(" "));
JavaMain.java · 58 줄
import java.io.BufferedReader;import java.io.InputStreamReader;import java.io.StreamTokenizer;import java.util.ArrayList;import java.util.List;public class Main { static int[] t; static int[][] deps; static boolean[] looked; // 이미 살핀 파일 static boolean[] rebuilt; // 이번에 다시 만든 파일 static List<Integer> order = new ArrayList<>(); // 다시 만든 차례 static void look(int x) { looked[x] = true; boolean stale = false; for (int a : deps[x]) { // 재료를 적힌 차례대로 먼저 살핀다 if (!looked[a]) look(a); if (rebuilt[a] || t[a] > t[x]) stale = true; } if (stale) { // 재료를 모두 살핀 뒤에야 자기를 만든다 rebuilt[x] = true; order.add(x); } } public static void main(String[] args) throws Exception { StreamTokenizer in = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in))); in.nextToken(); int n = (int) in.nval; in.nextToken(); int goal = (int) in.nval; t = new int[n + 1]; for (int i = 1; i <= n; i++) { in.nextToken(); t[i] = (int) in.nval; } deps = new int[n + 1][]; for (int i = 1; i <= n; i++) { in.nextToken(); int k = (int) in.nval; deps[i] = new int[k]; for (int j = 0; j < k; j++) { in.nextToken(); deps[i][j] = (int) in.nval; } } looked = new boolean[n + 1]; rebuilt = new boolean[n + 1]; look(goal); StringBuilder out = new StringBuilder(); out.append(order.size()).append('\n'); for (int i = 0; i < order.size(); i++) out.append(i > 0 ? " " : "").append(order.get(i)); if (!order.isEmpty()) out.append('\n'); System.out.print(out); }}
C#Main.cs · 50 줄
using System;using System.Collections.Generic;class Program{ static int[] t; static int[][] deps; static bool[] looked; // 이미 살핀 파일 static bool[] rebuilt; // 이번에 다시 만든 파일 static List<int> order = new List<int>(); // 다시 만든 차례 static void Look(int x) { looked[x] = true; bool stale = false; foreach (int a in deps[x]) // 재료를 적힌 차례대로 먼저 살핀다 { if (!looked[a]) Look(a); if (rebuilt[a] || t[a] > t[x]) stale = true; } if (stale) // 재료를 모두 살핀 뒤에야 자기를 만든다 { rebuilt[x] = true; order.Add(x); } } static void Main() { string[] data = Console.In.ReadToEnd().Split((char[])null, StringSplitOptions.RemoveEmptyEntries); int n = int.Parse(data[0]), goal = int.Parse(data[1]); t = new int[n + 1]; for (int i = 1; i <= n; i++) t[i] = int.Parse(data[1 + i]); deps = new int[n + 1][]; int pos = 2 + n; for (int i = 1; i <= n; i++) { int k = int.Parse(data[pos]); deps[i] = new int[k]; for (int j = 0; j < k; j++) deps[i][j] = int.Parse(data[pos + 1 + j]); pos += 1 + k; } looked = new bool[n + 1]; rebuilt = new bool[n + 1]; Look(goal); Console.WriteLine(order.Count); if (order.Count > 0) Console.WriteLine(string.Join(" ", order)); }}
C++main.cpp · 44 줄
#include <iostream>#include <vector>std::vector<int> t;std::vector<std::vector<int>> deps;std::vector<bool> looked; // 이미 살핀 파일std::vector<bool> rebuilt; // 이번에 다시 만든 파일std::vector<int> order; // 다시 만든 차례void look(int x) { looked[x] = true; bool stale = false; for (int a : deps[x]) { // 재료를 적힌 차례대로 먼저 살핀다 if (!looked[a]) look(a); if (rebuilt[a] || t[a] > t[x]) stale = true; } if (stale) { // 재료를 모두 살핀 뒤에야 자기를 만든다 rebuilt[x] = true; order.push_back(x); }}int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, goal; std::cin >> n >> goal; t.assign(n + 1, 0); for (int i = 1; i <= n; i++) std::cin >> t[i]; deps.assign(n + 1, {}); for (int i = 1; i <= n; i++) { int k; std::cin >> k; deps[i].resize(k); for (int &a : deps[i]) std::cin >> a; } looked.assign(n + 1, false); rebuilt.assign(n + 1, false); look(goal); std::cout << order.size() << '\n'; for (std::size_t i = 0; i < order.size(); i++) std::cout << (i ? " " : "") << order[i]; if (!order.empty()) std::cout << '\n';}
Cmain.c · 44 줄
#include <stdio.h>#define MAXN 5001#define MAXM 10000int t[MAXN];int start[MAXN + 1]; /* i번 파일의 재료는 dep[start[i]] … dep[start[i + 1] - 1] */int dep[MAXM + 1];int looked[MAXN]; /* 이미 살핀 파일 */int rebuilt[MAXN]; /* 이번에 다시 만든 파일 */int order[MAXN], made = 0;void look(int x) { looked[x] = 1; int stale = 0; for (int j = start[x]; j < start[x + 1]; j++) { /* 재료를 적힌 차례대로 먼저 살핀다 */ int a = dep[j]; if (!looked[a]) look(a); if (rebuilt[a] || t[a] > t[x]) stale = 1; } if (stale) { /* 재료를 모두 살핀 뒤에야 자기를 만든다 */ rebuilt[x] = 1; order[made++] = x; }}int main(void) { int n, goal; scanf("%d %d", &n, &goal); for (int i = 1; i <= n; i++) scanf("%d", &t[i]); int m = 0; for (int i = 1; i <= n; i++) { int k; scanf("%d", &k); start[i] = m; for (int j = 0; j < k; j++) scanf("%d", &dep[m++]); } start[n + 1] = m; look(goal); printf("%d\n", made); for (int i = 0; i < made; i++) printf(i + 1 < made ? "%d " : "%d\n", order[i]); return 0;}
Craykonmain.cray · 48 줄
첫줄 = 콘솔.수들읽기();n = 첫줄[0];goal = 첫줄[1];t = 콘솔.수들읽기(); // t[i - 1]: i번 파일을 고친 시각deps = [];반복 (i = 0; i < n; i++){ 줄 = 콘솔.수들읽기(); 재료 = []; 반복 (j = 1; j <= 줄[0]; j++) { 재료.넣기(줄[j] - 1); } deps.넣기(재료);}looked = 새목록(n, 거짓); // 이미 살핀 파일rebuilt = 새목록(n, 거짓); // 이번에 다시 만든 파일order = []; // 다시 만든 차례살피기(x){ looked[x] = 참; stale = 거짓; 각각 (a 에서 deps[x]) { 만약 (!looked[a]) { 살피기(a); } 만약 (rebuilt[a] || t[a] > t[x]) { stale = 참; } } 만약 (stale) { rebuilt[x] = 참; order.넣기(x + 1); }}살피기(goal - 1);콘솔.쓰기(order.개수);만약 (order.개수 > 0){ 콘솔.쓰기(order.잇기(" "));}