마을이 n개 있고 1번부터 n번까지 번호가 붙어 있다.
마을 사이에 길이 m개 있고, 길 하나 "a b"는 a번 마을과 b번 마을을 잇는다. 길은 양쪽으로 다닐 수 있다.
같은 두 마을을 잇는 길이 여러 개 있을 수 있고, 그런 길은 서로 다른 길로 친다.
마을마다 그 마을에 닿은 길에 차례를 매긴다. 입력에 먼저 나온 길이 앞이어서, 그 마을에 닿은 길 가운데 입력에 가장 먼저 나온 길이 그 마을의 1번째 길이다.
길 안내 쪽지가 q장 있다.
쪽지 한 장에는 출발 마을 s와 지시 k개 c₁, c₂, …, c_k가 적혀 있다.
여행자는 s번 마을에서 출발해 지시를 앞에서부터 하나씩 따른다.
지시 c를 따른다는 것은 지금 있는 마을의 c번째 길을 지나 그 길의 건너편 마을로 가는 것이다.
지금 있는 마을에 닿은 길이 c개보다 적으면 그 지시는 따를 수 없다. 여행자는 그 마을에서 멈추고 남은 지시를 모두 버린다.
쪽지마다 한 줄에, 여행자가 마지막에 있는 마을의 번호와 따른 지시의 수를 빈칸 하나로 띄워 출력하라.
입력
첫 줄에 n과 m이 빈칸 하나로 나뉘어 주어진다. 다음 m줄에 길이 한 줄에 하나씩 "a b"로 주어진다. 그다음 줄에 q가 주어지고, 다음 q줄에 쪽지가 한 줄에 한 장씩 "s k c₁ c₂ … c_k"로 빈칸 하나씩으로 나뉘어 주어진다. 2 ≤ n ≤ 50, 1 ≤ m ≤ 200, 1 ≤ a, b ≤ n, a ≠ b, 1 ≤ q ≤ 50, 1 ≤ s ≤ n, 1 ≤ k ≤ 50, 1 ≤ c ≤ 200
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
길 목록을 '마을마다 닿은 길의 건너편 마을 목록'(인접 목록)으로 바꿔 두면, 지시 하나를 roads[town][c - 1] 한 번으로 따를 수 있어요. 예시에서는 1번 마을이 2, 3이고 3번 마을이 2, 1, 4예요. 언어마다 갈리는 곳은 '빈 목록 n + 1개'를 만드는 법이에요. 함정 하나: Python [[]] * (n + 1)과 JS·TS new Array(n + 1).fill([])는 빈 목록을 n + 1개 만드는 것이 아니라 같은 목록 하나를 n + 1번 가리켜요. 모든 마을의 길이 한 목록에 섞여서 예시가 2 3, 2 4, 3 2가 돼요. Python은 [[] for _ in range(n + 1)], JS·TS는 Array.from({ length: n + 1 }, () => [])로 써요. C++ vector<vector<int>> roads(n + 1)과 크레이콘 새목록(n + 1, [])은 칸마다 따로 목록을 만들어 주고(다만 새목록(n, 사전())처럼 사전을 채우면 모든 칸이 같은 사전 하나를 가리켜요), Java와 C#은 반복문으로 칸마다 new ArrayList<>(), new List<int>()를 넣어요. C는 늘어나는 목록이 없어서 roads[51][200] 배열과 마을마다 길의 수를 세는 배열을 써요. 함정 둘: 길 "a b"를 a번 마을에만 적으면 b번 마을에서는 그 길이 보이지 않아요. 예시가 3 1, 2 0, 4 0이 돼요. 함정 셋: c번째 길은 0부터 세는 목록에서 c - 1번이에요. roads[town][c]로 읽으면 한 칸 뒤의 길을 타고, 예시의 첫 쪽지처럼 마지막 길을 고르면 목록 밖을 읽어요. Python은 IndexError로 멈춰요. 함정 넷: 길이 모자란 지시에서 멈추지 않고 그 지시만 건너뛰면, 예시의 둘째 쪽지가 마지막 지시까지 따라 1 3이 돼요. 길이 모자란지 아예 묻지 않으면 JS·TS는 배열 밖을 읽어도 오류 없이 undefined를 주어서 마을 번호가 undefined가 되고, 그다음 지시에서야 TypeError로 멈춰요. 한 줄에 수가 몇 개 올지 모르는 쪽지 줄은 Python·JS처럼 입력 전체를 빈칸으로 잘라 놓고 차례로 읽으면 편한데, 이때는 멈춘 뒤에도 읽는 자리를 k만큼 옮겨야 다음 쪽지가 밀리지 않아요. C와 C++도 남은 지시를 끝까지 읽어서 버려요.
Pythonmain.py · 31 줄
import sysdata = sys.stdin.read().split()pos = 0n, m = int(data[0]), int(data[1])pos = 2# roads[v] = v번 마을에 닿은 길의 건너편 마을들, 입력에 나온 차례대로# [[]] * (n + 1)로 만들면 모든 칸이 같은 목록 하나를 가리키므로 칸마다 새 목록을 만든다roads = [[] for _ in range(n + 1)]for _ in range(m): a, b = int(data[pos]), int(data[pos + 1]) pos += 2 roads[a].append(b) # 길은 양쪽으로 다니므로 두 마을 모두에 적는다 roads[b].append(a)q = int(data[pos])pos += 1out = []for _ in range(q): town, k = int(data[pos]), int(data[pos + 1]) pos += 2 followed = 0 for j in range(k): c = int(data[pos + j]) if c > len(roads[town]): # 그런 길이 없으면 거기서 멈춘다 break town = roads[town][c - 1] # c번째 길은 0부터 세면 c - 1번 followed += 1 pos += k # 버린 지시까지 건너뛴다 out.append(f"{town} {followed}")print("\n".join(out))
JavaScriptmain.js · 30 줄
const data = require("fs").readFileSync(0, "utf8").split(/\s+/).filter((s) => s !== "").map(Number);let pos = 0;const n = data[pos++];const m = data[pos++];// roads[v] = v번 마을에 닿은 길의 건너편 마을들, 입력에 나온 차례대로// new Array(n + 1).fill([])로 만들면 모든 칸이 같은 배열 하나를 가리키므로 칸마다 새 배열을 만든다const roads = Array.from({ length: n + 1 }, () => []);for (let i = 0; i < m; i++) { const a = data[pos++]; const b = data[pos++]; roads[a].push(b); // 길은 양쪽으로 다니므로 두 마을 모두에 적는다 roads[b].push(a);}const q = data[pos++];const out = [];for (let i = 0; i < q; i++) { let town = data[pos++]; const k = data[pos++]; let followed = 0; for (let j = 0; j < k; j++) { const c = data[pos + j]; if (c > roads[town].length) break; // 그런 길이 없으면 거기서 멈춘다 town = roads[town][c - 1]; // c번째 길은 0부터 세면 c - 1번 followed++; } pos += k; // 버린 지시까지 건너뛴다 out.push(`${town} ${followed}`);}console.log(out.join("\n"));
TypeScriptmain.ts · 32 줄
import { readFileSync } from "node:fs";const data: number[] = readFileSync(0, "utf8").split(/\s+/).filter((s: string): boolean => s !== "").map(Number);let pos = 0;const n: number = data[pos++];const m: number = data[pos++];// roads[v] = v번 마을에 닿은 길의 건너편 마을들, 입력에 나온 차례대로// new Array(n + 1).fill([])로 만들면 모든 칸이 같은 배열 하나를 가리키므로 칸마다 새 배열을 만든다const roads: number[][] = Array.from({ length: n + 1 }, (): number[] => []);for (let i = 0; i < m; i++) { const a: number = data[pos++]; const b: number = data[pos++]; roads[a].push(b); // 길은 양쪽으로 다니므로 두 마을 모두에 적는다 roads[b].push(a);}const q: number = data[pos++];const out: string[] = [];for (let i = 0; i < q; i++) { let town: number = data[pos++]; const k: number = data[pos++]; let followed = 0; for (let j = 0; j < k; j++) { const c: number = data[pos + j]; if (c > roads[town].length) break; // 그런 길이 없으면 거기서 멈춘다 town = roads[town][c - 1]; // c번째 길은 0부터 세면 c - 1번 followed++; } pos += k; // 버린 지시까지 건너뛴다 out.push(`${town} ${followed}`);}console.log(out.join("\n"));
JavaMain.java · 45 줄
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.List;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()); // roads.get(v) = v번 마을에 닿은 길의 건너편 마을들, 입력에 나온 차례대로 // 바깥 목록에 칸마다 new ArrayList<>()를 하나씩 넣어야 한다 List<List<Integer>> roads = new ArrayList<>(); for (int v = 0; v <= n; v++) { roads.add(new ArrayList<>()); } for (int i = 0; i < m; i++) { st = new StringTokenizer(in.readLine()); int a = Integer.parseInt(st.nextToken()); int b = Integer.parseInt(st.nextToken()); roads.get(a).add(b); // 길은 양쪽으로 다니므로 두 마을 모두에 적는다 roads.get(b).add(a); } int q = Integer.parseInt(in.readLine().trim()); StringBuilder out = new StringBuilder(); for (int i = 0; i < q; i++) { st = new StringTokenizer(in.readLine()); int town = Integer.parseInt(st.nextToken()); int k = Integer.parseInt(st.nextToken()); int followed = 0; for (int j = 0; j < k; j++) { int c = Integer.parseInt(st.nextToken()); if (c > roads.get(town).size()) break; // 그런 길이 없으면 거기서 멈춘다 town = roads.get(town).get(c - 1); // c번째 길은 0부터 세면 c - 1번 followed++; } out.append(town).append(' ').append(followed).append('\n'); } System.out.print(out); }}
C#Main.cs · 47 줄
using System;using System.Collections.Generic;using System.Text;class Program{ static void Main() { string[] first = Console.ReadLine().Trim().Split(' '); int n = int.Parse(first[0]); int m = int.Parse(first[1]); // roads[v] = v번 마을에 닿은 길의 건너편 마을들, 입력에 나온 차례대로 // new List<int>[n + 1]만 하면 칸이 모두 null이라서 칸마다 new List<int>()를 넣어야 한다 var roads = new List<int>[n + 1]; for (int v = 0; v <= n; v++) { roads[v] = new List<int>(); } for (int i = 0; i < m; i++) { string[] p = Console.ReadLine().Trim().Split(' '); int a = int.Parse(p[0]); int b = int.Parse(p[1]); roads[a].Add(b); // 길은 양쪽으로 다니므로 두 마을 모두에 적는다 roads[b].Add(a); } int q = int.Parse(Console.ReadLine().Trim()); var sb = new StringBuilder(); for (int i = 0; i < q; i++) { string[] p = Console.ReadLine().Trim().Split(' '); int town = int.Parse(p[0]); int k = int.Parse(p[1]); int followed = 0; for (int j = 0; j < k; j++) { int c = int.Parse(p[2 + j]); if (c > roads[town].Count) break; // 그런 길이 없으면 거기서 멈춘다 town = roads[town][c - 1]; // c번째 길은 0부터 세면 c - 1번 followed++; } sb.Append(town).Append(' ').Append(followed).Append('\n'); } Console.Write(sb); }}
C++main.cpp · 37 줄
#include <iostream>#include <vector>using namespace std;int main() { int n, m, q; cin >> n >> m; // roads[v] = v번 마을에 닿은 길의 건너편 마을들, 입력에 나온 차례대로 // vector<vector<int>>는 칸마다 따로 빈 vector를 만들어 준다 vector<vector<int>> roads(n + 1); for (int i = 0; i < m; i++) { int a, b; cin >> a >> b; roads[a].push_back(b); // 길은 양쪽으로 다니므로 두 마을 모두에 적는다 roads[b].push_back(a); } cin >> q; for (int i = 0; i < q; i++) { int town, k, followed = 0; bool stopped = false; cin >> town >> k; for (int j = 0; j < k; j++) { int c; cin >> c; // 멈춘 뒤에도 남은 지시는 읽어서 버려야 다음 쪽지가 밀리지 않는다 if (stopped) continue; if (c > (int)roads[town].size()) { // 그런 길이 없으면 거기서 멈춘다 stopped = true; continue; } town = roads[town][c - 1]; // c번째 길은 0부터 세면 c - 1번 followed++; } cout << town << ' ' << followed << '\n'; } return 0;}
Cmain.c · 39 줄
#include <stdio.h>#define MAXN 50#define MAXM 200int main(void) { int n, m, q; /* roads[v][i] = v번 마을의 (i + 1)번째 길 건너편 마을, count[v] = v번 마을에 닿은 길의 수 */ /* C에는 늘어나는 목록이 없어서, 한 마을에 길이 모두 몰려도 되도록 칸을 넉넉히 잡는다 */ static int roads[MAXN + 1][MAXM]; static int count[MAXN + 1]; scanf("%d %d", &n, &m); for (int i = 0; i < m; i++) { int a, b; scanf("%d %d", &a, &b); roads[a][count[a]++] = b; /* 길은 양쪽으로 다니므로 두 마을 모두에 적는다 */ roads[b][count[b]++] = a; } scanf("%d", &q); for (int i = 0; i < q; i++) { int town, k, followed = 0, stopped = 0; scanf("%d %d", &town, &k); for (int j = 0; j < k; j++) { int c; scanf("%d", &c); /* 멈춘 뒤에도 남은 지시는 읽어서 버려야 다음 쪽지가 밀리지 않는다 */ if (stopped) continue; if (c > count[town]) { /* 그런 길이 없으면 거기서 멈춘다 */ stopped = 1; continue; } town = roads[town][c - 1]; /* c번째 길은 0부터 세면 c - 1번 */ followed++; } printf("%d %d\n", town, followed); } return 0;}
Craykonmain.cray · 34 줄
첫줄 = 콘솔.수들읽기();n = 첫줄[0];m = 첫줄[1];// roads[v] = v번 마을에 닿은 길의 건너편 마을들, 입력에 나온 차례대로// 새목록(개수, [])은 칸마다 따로 빈 목록을 만들어 준다roads = 새목록(n + 1, []);반복 (i = 0; i < m; i++){ 길 = 콘솔.수들읽기(); roads[길[0]].넣기(길[1]); // 길은 양쪽으로 다니므로 두 마을 모두에 적는다 roads[길[1]].넣기(길[0]);}q = 콘솔.수들읽기()[0];out = [];반복 (i = 0; i < q; i++){ 쪽지 = 콘솔.수들읽기(); town = 쪽지[0]; k = 쪽지[1]; followed = 0; 반복 (j = 0; j < k; j++) { c = 쪽지[2 + j]; 만약 (c > roads[town].개수) { 그만; } town = roads[town][c - 1]; // c번째 길은 0부터 세면 c - 1번 followed += 1; } out.넣기(town + " " + followed);}콘솔.쓰기(out.잇기("\n"));