집에 방이 n개 있고 1번부터 n번까지 번호가 붙어 있다.
방마다 그 방과 문 하나로 바로 이어진 방의 번호가 주어진다. 문은 양쪽으로 다닐 수 있어서, a번 방의 목록에 b가 있으면 b번 방의 목록에도 a가 있다.
술래는 1번 방에서 찾기 시작하고, 친구는 t번 방에 숨어 있다.
술래는 다음 규칙을 되풀이해 움직인다.
지금 있는 방과 바로 이어진 방 가운데 아직 한 번도 들어가 보지 않은 방이 있으면, 그 가운데 번호가 가장 작은 방으로 들어간다.
그런 방이 없으면, 지금 있는 방에 처음 들어올 때 떠나온 방으로 되돌아간다.
t번 방에 들어가면 친구를 찾은 것이므로 바로 멈춘다.
1번 방에 있는데 들어가 볼 방이 없으면 친구를 찾지 못한 채 멈춘다.
1번 방은 처음부터 들어가 본 방으로 친다.
첫 줄에 술래가 문을 지난 횟수를 출력하라. 새 방에 들어갈 때와 되돌아갈 때 모두 한 번씩 센다.
둘째 줄에 술래가 있던 방의 번호를 처음의 1번부터 차례대로 빈칸 하나로 띄워 출력하라. 되돌아가서 다시 선 방도 그때마다 다시 적는다.
입력
첫 줄에 n과 t가 빈칸 하나로 나뉘어 주어진다. 다음 n줄 가운데 i번째 줄에는 i번 방과 이어진 방의 수 k와 그 방들의 번호 k개가 빈칸 하나씩으로 나뉘어 주어진다. 이어진 방이 없으면 그 줄에는 0만 있다. 2 ≤ n ≤ 30, 2 ≤ t ≤ n, 0 ≤ k ≤ n − 1. 한 줄에 적힌 방 번호는 모두 서로 다르고 자기 번호는 없으며, 정해진 순서 없이 주어진다
출력
두 줄. 첫 줄에 문을 지난 횟수, 둘째 줄에 술래가 있던 방의 번호를 차례대로
예시 1 · stdin
6 5
2 3 2
2 1 4
2 1 5
1 2
2 3 6
1 5
stdout
6
1 2 4 2 1 3 5
예시 2 · stdin
10 9
2 10 2
1 1
1 9
0
0
0
0
0
1 3
1 1
stdout
4
1 2 1 10 1
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
재귀 함수가 '찾았다'를 돌려주게 하면 깊이 들어간 곳에서도 한 번에 빠져나올 수 있어요. if search(next): return True처럼 돌려받은 값이 참이면 바로 참을 돌려주고, 거짓일 때만 '이 방으로 되돌아왔다'를 적어요. 이 꼴은 여덟 풀이가 모두 같고(C는 bool 대신 1과 0), 언어마다 다른 것은 이어진 방을 번호 순으로 정렬하는 법이에요. Python sorted(nums), Java Arrays.sort(int[]), C# Array.Sort(int[]), C++ std::sort, 크레이콘 목록.정렬()은 수의 크기로 정렬해요. C qsort는 견주는 함수를 꼭 넘겨야 해요. 함정 하나: JS·TS의 sort()는 견주는 함수를 넘기지 않으면 수 배열도 문자열로 바꿔 견줘서 10이 2보다 앞에 와요. 예시 2에서 1번 방의 목록 10, 2가 그대로 남아 술래가 10번 방부터 들어가고, 둘째 줄이 1 10 1 2 1이 돼요. sort((a, b) => a - b)로 써요. 정렬을 아예 하지 않아도 예시 2는 똑같이 틀리고, 예시 1은 3번 방부터 들어가서 2와 1 3 5가 나와요. 함정 둘: 재귀 호출이 돌려준 값을 보지 않으면 친구를 찾은 뒤에도 술래가 되돌아가요. 예시 1의 둘째 줄 끝에 3 1이 더 붙고 첫 줄이 8이 돼요. 함정 셋: 처음 들어간 방만 적으면(흔히 보는 '방문 순서' 출력) 되돌아간 걸음이 빠져요. 예시 1이 4와 1 2 4 3 5가 되는데, 4번 방에서 3번 방으로 바로 가는 문은 없어요. 방이 30개뿐이라 재귀 깊이는 어느 언어에서도 걱정할 필요가 없어요.
Pythonmain.py · 30 줄
import syslines = sys.stdin.read().split("\n")n, target = map(int, lines[0].split())doors = [[] for _ in range(n + 1)] # doors[r] = r번 방과 문으로 이어진 방들for r in range(1, n + 1): nums = list(map(int, lines[r].split())) doors[r] = sorted(nums[1:]) # 번호가 작은 방부터 들어가 보려고 정렬해 둔다visited = [False] * (n + 1)walk = [] # 술래가 있던 방을 차례대로 적는다def search(room): """room에 들어가서 찾는다. 친구를 찾았으면 True를 돌려준다.""" visited[room] = True walk.append(room) if room == target: return True for nxt in doors[room]: if not visited[nxt]: if search(nxt): return True # 찾았으면 되돌아가지 않고 바로 끝낸다 walk.append(room) # 못 찾고 이 방으로 되돌아왔다 return Falsesearch(1)print(len(walk) - 1)print(" ".join(map(str, walk)))
JavaScriptmain.js · 29 줄
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [n, target] = lines[0].trim().split(" ").map(Number);const doors = [[]]; // doors[r] = r번 방과 문으로 이어진 방들(0번은 쓰지 않는다)for (let r = 1; r <= n; r++) { const nums = lines[r].trim().split(" ").map(Number); // 번호가 작은 방부터 들어가 보려고 정렬해 둔다. sort()만 쓰면 문자열로 견주므로 함수를 넘긴다 doors.push(nums.slice(1).sort((a, b) => a - b));}const visited = new Array(n + 1).fill(false);const walk = []; // 술래가 있던 방을 차례대로 적는다// room에 들어가서 찾는다. 친구를 찾았으면 true를 돌려준다function search(room) { visited[room] = true; walk.push(room); if (room === target) return true; for (const next of doors[room]) { if (!visited[next]) { if (search(next)) return true; // 찾았으면 되돌아가지 않고 바로 끝낸다 walk.push(room); // 못 찾고 이 방으로 되돌아왔다 } } return false;}search(1);console.log(walk.length - 1);console.log(walk.join(" "));
TypeScriptmain.ts · 31 줄
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const [n, target]: number[] = lines[0].trim().split(" ").map(Number);const doors: number[][] = [[]]; // doors[r] = r번 방과 문으로 이어진 방들(0번은 쓰지 않는다)for (let r = 1; r <= n; r++) { const nums: number[] = lines[r].trim().split(" ").map(Number); // 번호가 작은 방부터 들어가 보려고 정렬해 둔다. sort()만 쓰면 문자열로 견주므로 함수를 넘긴다 doors.push(nums.slice(1).sort((a: number, b: number): number => a - b));}const visited: boolean[] = new Array<boolean>(n + 1).fill(false);const walk: number[] = []; // 술래가 있던 방을 차례대로 적는다// room에 들어가서 찾는다. 친구를 찾았으면 true를 돌려준다function search(room: number): boolean { visited[room] = true; walk.push(room); if (room === target) return true; for (const next of doors[room]) { if (!visited[next]) { if (search(next)) return true; // 찾았으면 되돌아가지 않고 바로 끝낸다 walk.push(room); // 못 찾고 이 방으로 되돌아왔다 } } return false;}search(1);console.log(walk.length - 1);console.log(walk.join(" "));
JavaMain.java · 53 줄
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayList;import java.util.Arrays;import java.util.List;public class Main { static int target; static int[][] doors; // doors[r] = r번 방과 문으로 이어진 방들 static boolean[] visited; static List<Integer> walk = new ArrayList<>(); // 술래가 있던 방을 차례대로 적는다 // room에 들어가서 찾는다. 친구를 찾았으면 true를 돌려준다 static boolean search(int room) { visited[room] = true; walk.add(room); if (room == target) return true; for (int next : doors[room]) { if (!visited[next]) { if (search(next)) return true; // 찾았으면 되돌아가지 않고 바로 끝낸다 walk.add(room); // 못 찾고 이 방으로 되돌아왔다 } } return false; } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String[] first = in.readLine().trim().split(" "); int n = Integer.parseInt(first[0]); target = Integer.parseInt(first[1]); doors = new int[n + 1][]; visited = new boolean[n + 1]; for (int r = 1; r <= n; r++) { String[] parts = in.readLine().trim().split(" "); int k = Integer.parseInt(parts[0]); doors[r] = new int[k]; for (int i = 0; i < k; i++) { doors[r][i] = Integer.parseInt(parts[i + 1]); } Arrays.sort(doors[r]); // int[]는 수의 크기로 정렬된다 } search(1); StringBuilder out = new StringBuilder(); out.append(walk.size() - 1).append('\n'); for (int i = 0; i < walk.size(); i++) { if (i > 0) out.append(' '); out.append(walk.get(i)); } System.out.println(out); }}
C#Main.cs · 50 줄
using System;using System.Collections.Generic;class Program{ static int target; static int[][] doors; // doors[r] = r번 방과 문으로 이어진 방들 static bool[] visited; static List<int> walk = new List<int>(); // 술래가 있던 방을 차례대로 적는다 // room에 들어가서 찾는다. 친구를 찾았으면 true를 돌려준다 static bool Search(int room) { visited[room] = true; walk.Add(room); if (room == target) return true; foreach (int next in doors[room]) { if (!visited[next]) { if (Search(next)) return true; // 찾았으면 되돌아가지 않고 바로 끝낸다 walk.Add(room); // 못 찾고 이 방으로 되돌아왔다 } } return false; } static void Main() { string[] first = Console.ReadLine().Trim().Split(' '); int n = int.Parse(first[0]); target = int.Parse(first[1]); doors = new int[n + 1][]; visited = new bool[n + 1]; for (int r = 1; r <= n; r++) { string[] parts = Console.ReadLine().Trim().Split(' '); int k = int.Parse(parts[0]); doors[r] = new int[k]; for (int i = 0; i < k; i++) { doors[r][i] = int.Parse(parts[i + 1]); } Array.Sort(doors[r]); // int[]는 수의 크기로 정렬된다 } Search(1); Console.WriteLine(walk.Count - 1); Console.WriteLine(string.Join(" ", walk)); }}
C++main.cpp · 45 줄
#include <algorithm>#include <iostream>#include <vector>using namespace std;int target;vector<vector<int>> doors; // doors[r] = r번 방과 문으로 이어진 방들vector<bool> visited;vector<int> walk; // 술래가 있던 방을 차례대로 적는다// room에 들어가서 찾는다. 친구를 찾았으면 true를 돌려준다bool search(int room) { visited[room] = true; walk.push_back(room); if (room == target) return true; for (int next : doors[room]) { if (!visited[next]) { if (search(next)) return true; // 찾았으면 되돌아가지 않고 바로 끝낸다 walk.push_back(room); // 못 찾고 이 방으로 되돌아왔다 } } return false;}int main() { int n; cin >> n >> target; doors.resize(n + 1); visited.assign(n + 1, false); for (int r = 1; r <= n; r++) { int k; cin >> k; doors[r].resize(k); for (int &room : doors[r]) cin >> room; sort(doors[r].begin(), doors[r].end()); // 번호가 작은 방부터 } search(1); cout << walk.size() - 1 << '\n'; for (size_t i = 0; i < walk.size(); i++) { if (i > 0) cout << ' '; cout << walk[i]; } cout << '\n'; return 0;}
Cmain.c · 48 줄
#include <stdio.h>#include <stdlib.h>#define MAXN 30static int n, target;static int doors[MAXN + 1][MAXN]; /* doors[r] = r번 방과 문으로 이어진 방들 */static int door_count[MAXN + 1];static int visited[MAXN + 1];static int walk[2 * MAXN]; /* 술래가 있던 방을 차례대로 적는다(많아야 2n - 1개) */static int walk_len = 0;static int compare_ints(const void *a, const void *b) { return *(const int *)a - *(const int *)b; /* 방 번호는 1~30이라 빼도 넘치지 않는다 */}/* room에 들어가서 찾는다. 친구를 찾았으면 1을 돌려준다 */static int search(int room) { visited[room] = 1; walk[walk_len++] = room; if (room == target) return 1; for (int i = 0; i < door_count[room]; i++) { int next = doors[room][i]; if (!visited[next]) { if (search(next)) return 1; /* 찾았으면 되돌아가지 않고 바로 끝낸다 */ walk[walk_len++] = room; /* 못 찾고 이 방으로 되돌아왔다 */ } } return 0;}int main(void) { scanf("%d %d", &n, &target); for (int r = 1; r <= n; r++) { scanf("%d", &door_count[r]); for (int i = 0; i < door_count[r]; i++) { scanf("%d", &doors[r][i]); } qsort(doors[r], door_count[r], sizeof(int), compare_ints); } search(1); printf("%d\n", walk_len - 1); for (int i = 0; i < walk_len; i++) { printf(i > 0 ? " %d" : "%d", walk[i]); } printf("\n"); return 0;}
Craykonmain.cray · 40 줄
첫줄 = 콘솔.수들읽기();n = 첫줄[0];target = 첫줄[1];doors = [[]]; // doors[r] = r번 방과 문으로 이어진 방들(0번은 쓰지 않는다)반복 (r = 1; r <= n; r++){ nums = 콘솔.수들읽기(); rooms = nums.부분목록(1, nums[0]); rooms.정렬(); // 수 목록은 수의 크기로 정렬된다. 번호가 작은 방부터 들어가 본다 doors.넣기(rooms);}visited = 새목록(n + 1, 거짓);walk = []; // 술래가 있던 방을 차례대로 적는다// room에 들어가서 찾는다. 친구를 찾았으면 참을 돌려준다찾기(room){ visited[room] = 참; walk.넣기(room); 만약 (room == target) { 돌려주기 참; } 각각 (next 에서 doors[room]) { 만약 (!visited[next]) { 만약 (찾기(next)) { 돌려주기 참; // 찾았으면 되돌아가지 않고 바로 끝낸다 } walk.넣기(room); // 못 찾고 이 방으로 되돌아왔다 } } 돌려주기 거짓;}찾기(1);콘솔.쓰기(walk.개수 - 1);콘솔.쓰기(walk.잇기(" "));