A house has n rooms numbered 1 to n.
For each room you are given the numbers of the rooms joined to it directly by one door. Doors work both ways, so if b is in the list of room a, then a is in the list of room b.
The seeker starts in room 1, and a friend is hiding in room t.
The seeker moves by repeating these rules.
If some room joined directly to the current room has never been entered, the seeker enters the one with the smallest number among them.
If there is no such room, the seeker goes back to the room they left when they first entered the current room.
On entering room t the friend is found, so the seeker stops at once.
If the seeker is in room 1 and there is no room left to enter, the seeker stops without finding the friend.
Room 1 counts as already entered from the start.
On the first line print how many times the seeker passed through a door. Entering a new room and going back each count once.
On the second line print the numbers of the rooms the seeker was in, in order, starting with the first 1 and separated by single spaces. A room the seeker goes back to is written again each time.
Input
The first line has n and t separated by one space. Of the next n lines, the i-th has the number k of rooms joined to room i followed by the k room numbers, separated by single spaces. If no room is joined to it, the line has just 0. 2 ≤ n ≤ 30, 2 ≤ t ≤ n, 0 ≤ k ≤ n − 1. The room numbers on one line are all different, never include the room itself, and come in no particular order
Output
Two lines. The number of door passes on the first line, and the rooms the seeker was in, in order, on the second
Example 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
Example 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
Error List00F8 ↓ · ⇧F8 ↑
Input (stdin)
When you run, these lines are fed to input()/stdin in order (the program doesn't stop to ask).
$ Ready
Open this on a computer to write and run code. On mobile you can read the problem and the solutions.
In other languagesShow solutions by language · 8 languages
If the recursive function returns 'found', you can get out at once even from deep inside. As in if search(next): return True, return true immediately when the value that came back is true, and write 'came back to this room' only when it is false. This shape is the same in all eight solutions (C uses 1 and 0 instead of bool); what differs by language is how to sort the joined rooms by number. Python sorted(nums), Java Arrays.sort(int[]), C# Array.Sort(int[]), C++ std::sort and Craykon list.Sort() sort by numeric value. C qsort always needs a comparing function. Trap one: JS/TS sort() without a comparing function converts even an array of numbers to strings to compare, so 10 comes before 2. In example 2 the list 10, 2 of room 1 stays as it is, the seeker enters room 10 first, and the second line becomes 1 10 1 2 1. Write sort((a, b) => a - b). Not sorting at all gets example 2 wrong in the same way, and in example 1 the seeker enters room 3 first, giving 2 and 1 3 5. Trap two: if you ignore the value the recursive call returns, the seeker walks back even after finding the friend. In example 1 an extra 3 1 is added to the end of the second line and the first line becomes 8. Trap three: if you write only the rooms entered for the first time (the usual 'visit order' output), the steps back are missing. Example 1 becomes 4 and 1 2 4 3 5, although no door leads straight from room 4 to room 3. With only 30 rooms, recursion depth is nothing to worry about in any of the languages.
Pythonmain.py · 30 lines
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 lines
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 lines
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 lines
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 lines
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 lines
#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 lines
#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 lines
첫줄 = Console.ReadNumbers();n = 첫줄[0];target = 첫줄[1];doors = [[]]; // doors[r] = r번 방과 문으로 이어진 방들(0번은 쓰지 않는다)for (r = 1; r <= n; r++){ nums = Console.ReadNumbers(); rooms = nums.GetRange(1, nums[0]); rooms.Sort(); // 수 목록은 수의 크기로 정렬된다. 번호가 작은 방부터 들어가 본다 doors.Add(rooms);}visited = NewList(n + 1, false);walk = []; // 술래가 있던 방을 차례대로 적는다// room에 들어가서 찾는다. 친구를 찾았으면 참을 돌려준다찾기(room){ visited[room] = true; walk.Add(room); if (room == target) { return true; } foreach (next in doors[room]) { if (!visited[next]) { if (찾기(next)) { return true; // 찾았으면 되돌아가지 않고 바로 끝낸다 } walk.Add(room); // 못 찾고 이 방으로 되돌아왔다 } } return false;}찾기(1);Console.WriteLine(walk.Count - 1);Console.WriteLine(walk.Join(" "));