R줄 C칸짜리 동굴 지도가 주어진다.
'.'은 빈칸, '#'은 바위, 'S'는 탐험가가 처음 서 있는 빈칸, 영어 소문자는 그 글자의 열쇠가 놓인 빈칸, 'S'를 뺀 영어 대문자는 문이다.
대문자 문은 같은 글자의 소문자 열쇠를 이미 가지고 있을 때만 들어갈 수 있다(예: 'B' 문에는 'b' 열쇠가 있어야 한다).
열쇠는 그 칸에 처음 들어갈 때 줍고, 한 번 주운 열쇠는 계속 가지고 있다.
탐험가는 처음 칸을 가 본 칸으로 표시하고 다음을 되풀이한다.
지금 칸에서 위, 오른쪽, 아래, 왼쪽 차례로 이웃 칸을 살펴, 지도 안이고, 바위가 아니고, 아직 가 보지 않았고, 들어갈 수 있는 첫 칸으로 한 칸 움직인다. 그 칸은 가 본 칸으로 표시한다.
그런 이웃이 없으면, 지금 칸에 처음 들어올 때 떠났던 칸으로 한 칸 되돌아간다.
되돌아간 칸에서도 위쪽부터 다시 살핀다.
처음 칸에서 갈 이웃이 없으면 탐험을 마친다.
앞으로 가는 것과 되돌아가는 것 모두 한 번 움직인 것으로 센다.
첫째 줄에 움직인 횟수 T와 가 본 칸의 수(처음 칸 포함)를 빈칸으로 나눠 출력하라.
둘째 줄에 새로 주운 열쇠의 글자를 주운 차례대로 이어 출력하라(이미 가진 글자의 열쇠를 또 주운 것은 적지 않는다). 하나도 없으면 '-'를 출력한다.
다음으로 질문 t마다, t번 움직인 직후 탐험가가 있는 칸의 줄 번호와 칸 번호(위·왼쪽이 1 1)를 한 줄에 출력하라.
0번 움직인 직후는 처음 칸이고, t가 T보다 크면 탐험을 마친 칸(처음 칸)이다.
입력
첫 줄에 R과 C, 다음 R줄에 길이 C인 지도 문자열, 다음 줄에 질문 수 Q, 다음 줄에 질문 t Q개가 빈칸으로 나뉘어 주어진다. 1 ≤ R, C ≤ 50, 'S'는 정확히 하나, 1 ≤ Q ≤ 100, 0 ≤ t ≤ 10,000.
출력
첫째 줄에 T와 가 본 칸 수, 둘째 줄에 주운 열쇠 글자들 또는 '-', 다음 Q줄에 줄마다 '줄 칸'
예시 1 · stdin
3 4
S.A.
.#b#
a...
4
0 3 10 100
stdout
18 10
ab
1 1
2 1
1 3
1 1
예시 2 · stdin
3 3
#A#
#Sa
###
6
0 1 2 3 4 5
stdout
4 3
a
2 2
2 3
2 2
1 2
2 2
2 2
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
벽을 더듬으며 막히면 돌아오는 탐험은 깊이 우선 탐색(DFS)이고, '지금까지 들어온 길'을 스택으로 들고 다니면 돼요: 앞으로 가면 넣고(push), 막히면 꺼내서(pop) 새 맨 위 칸으로 돌아가요. 스택에 처음 칸만 남았는데 갈 곳이 없으면 끝이에요. 가장 흔한 함정은 보통의 재귀 DFS(for 방향마다 재귀 호출)를 그대로 쓰는 것이에요: 돌아온 뒤 다음 방향부터 이어서 살피니, 그사이 주운 열쇠로 열린 앞쪽 방향의 문을 다시 보지 않아요(예시 2에서 위쪽 'A' 문을 영영 못 열어 T가 2가 돼요). 이 문제는 칸에 설 때마다 위쪽부터 다시 살피라고 정했으니, 스택 맨 위 칸에서 매번 네 방향을 처음부터 보면 돼요(가 본 칸 표시가 있어서 한 칸에서 다시 보는 일은 많아야 네 방향씩이라 빨라요). 두 번째 함정은 깊이예요: 막힘없는 50×50 동굴에서는 길이 2,500칸까지 깊어져서, 재귀로 풀면 Python 기본 재귀 한도(1,000)를 넘고 크레이콘도 몇천 단계에서 멈출 수 있어요 — 그래서 직접 만든 스택이 안전해요. 그 밖에: 되돌아가는 걸음도 움직임으로 세기, t가 T보다 클 때 처음 칸으로 답하기(배열 끝을 넘어 읽지 않기), 줄·칸 번호는 1부터. 언어마다: Python 목록 append/pop과 for … else(break 없이 끝나면 else), Java ArrayDeque<int[]>의 push/pop/peek, C# Stack<(int y, int x)>와 Array.FindIndex, HashSet.Add가 새로 넣을 때만 true라 열쇠를 처음 주웠는지 바로 알 수 있어요. C++ std::vector를 스택으로(push_back/pop_back/back)와 std::find_if, C는 칸 번호 배열과 맨 위 자리 변수, JavaScript·TypeScript는 배열 push/pop과 STEPS.find(…)(없으면 undefined). 크레이콘은 칸을 수 하나 y * c + x로 펴서 목록 path에 넣기/자리빼기(개수 - 1)하고, 문의 열쇠는 ch.소문자로변환()으로 찾아요. 크레이콘 목록 범위 밖 읽기는 실행 오류라 수학.작은수(t, moves)로 끝을 막아요.
Pythonmain.py · 54 줄
import sysdata = sys.stdin.read().split("\n")r, c = map(int, data[0].split())grid = [data[1 + y].strip() for y in range(r)]q = int(data[1 + r])queries = list(map(int, data[2 + r].split()))STEPS = ((-1, 0), (0, 1), (1, 0), (0, -1)) # 위, 오른쪽, 아래, 왼쪽start = next((y, x) for y in range(r) for x in range(c) if grid[y][x] == "S")visited = [[False] * c for _ in range(r)]visited[start[0]][start[1]] = Truekeys = set()picked = [] # 새로 얻은 열쇠(얻은 차례)path = [start] # 지금까지 들어온 길(스택): 맨 위가 지금 자리log = [start] # log[t] = t번 움직인 뒤의 자리def can_enter(y, x): if not (0 <= y < r and 0 <= x < c) or visited[y][x]: return False ch = grid[y][x] if ch == "#": return False if ch.isupper(): return ch.lower() in keys # 문은 맞는 열쇠가 있어야 들어간다 return Truewhile True: y, x = path[-1] # 자리에 설 때마다(돌아왔을 때도) 위쪽부터 다시 살핀다 — 그사이 얻은 열쇠로 열리는 문이 있을 수 있다 for dy, dx in STEPS: ny, nx = y + dy, x + dx if can_enter(ny, nx): visited[ny][nx] = True ch = grid[ny][nx] if ch.islower() and ch not in keys: keys.add(ch) picked.append(ch) path.append((ny, nx)) break else: if len(path) == 1: break # 처음 자리에서 더 갈 곳이 없으면 멈춘다 path.pop() # 왔던 칸으로 한 칸 되돌아간다 log.append(path[-1])moves = len(log) - 1out = [f"{moves} {sum(map(sum, visited))}", "".join(picked) or "-"]for t in queries: y, x = log[min(t, moves)] # 멈춘 뒤에는 처음 자리에 그대로 있다 out.append(f"{y + 1} {x + 1}")print("\n".join(out))
JavaScriptmain.js · 54 줄
const data = require("fs").readFileSync(0, "utf8").split("\n");const [r, c] = data[0].trim().split(/\s+/).map(Number);const grid = [];for (let y = 0; y < r; y++) grid.push(data[1 + y].trim());const queries = data[2 + r].trim().split(/\s+/).map(Number);const STEPS = [[-1, 0], [0, 1], [1, 0], [0, -1]]; // 위, 오른쪽, 아래, 왼쪽let start = null;for (let y = 0; y < r; y++) for (let x = 0; x < c; x++) if (grid[y][x] === "S") start = [y, x];const visited = Array.from({ length: r }, () => new Array(c).fill(false));visited[start[0]][start[1]] = true;const keys = new Set();let picked = ""; // 새로 얻은 열쇠(얻은 차례)const path = [start]; // 지금까지 들어온 길(스택): 맨 끝이 지금 자리const log = [start]; // log[t] = t번 움직인 뒤의 자리const isUpper = (ch) => ch >= "A" && ch <= "Z";const isLower = (ch) => ch >= "a" && ch <= "z";function canEnter(y, x) { if (y < 0 || y >= r || x < 0 || x >= c || visited[y][x]) return false; const ch = grid[y][x]; if (ch === "#") return false; if (isUpper(ch)) return keys.has(ch.toLowerCase()); // 문은 맞는 열쇠가 있어야 들어간다 return true;}while (true) { const [y, x] = path[path.length - 1]; // 자리에 설 때마다(돌아왔을 때도) 위쪽부터 다시 살핀다 — 그사이 얻은 열쇠로 열리는 문이 있을 수 있다 const step = STEPS.find(([dy, dx]) => canEnter(y + dy, x + dx)); if (step !== undefined) { const ny = y + step[0], nx = x + step[1]; visited[ny][nx] = true; const ch = grid[ny][nx]; if (isLower(ch) && !keys.has(ch)) { keys.add(ch); picked += ch; } path.push([ny, nx]); } else { if (path.length === 1) break; // 처음 자리에서 더 갈 곳이 없으면 멈춘다 path.pop(); // 왔던 칸으로 한 칸 되돌아간다 } log.push(path[path.length - 1]);}const moves = log.length - 1;const seen = visited.flat().filter(Boolean).length;const out = [`${moves} ${seen}`, picked || "-"];for (const t of queries) { const [y, x] = log[Math.min(t, moves)]; // 멈춘 뒤에는 처음 자리에 그대로 있다 out.push(`${y + 1} ${x + 1}`);}console.log(out.join("\n"));
TypeScriptmain.ts · 57 줄
import { readFileSync } from "node:fs";type Cell = [number, number];const data: string[] = readFileSync(0, "utf8").split("\n");const [r, c] = data[0].trim().split(/\s+/).map(Number);const grid: string[] = [];for (let y = 0; y < r; y++) grid.push(data[1 + y].trim());const queries = data[2 + r].trim().split(/\s+/).map(Number);const STEPS: Cell[] = [[-1, 0], [0, 1], [1, 0], [0, -1]]; // 위, 오른쪽, 아래, 왼쪽let start: Cell = [0, 0];for (let y = 0; y < r; y++) for (let x = 0; x < c; x++) if (grid[y][x] === "S") start = [y, x];const visited: boolean[][] = Array.from({ length: r }, () => new Array<boolean>(c).fill(false));visited[start[0]][start[1]] = true;const keys = new Set<string>();let picked = ""; // 새로 얻은 열쇠(얻은 차례)const path: Cell[] = [start]; // 지금까지 들어온 길(스택): 맨 끝이 지금 자리const log: Cell[] = [start]; // log[t] = t번 움직인 뒤의 자리const isUpper = (ch: string): boolean => ch >= "A" && ch <= "Z";const isLower = (ch: string): boolean => ch >= "a" && ch <= "z";function canEnter(y: number, x: number): boolean { if (y < 0 || y >= r || x < 0 || x >= c || visited[y][x]) return false; const ch = grid[y][x]; if (ch === "#") return false; if (isUpper(ch)) return keys.has(ch.toLowerCase()); // 문은 맞는 열쇠가 있어야 들어간다 return true;}while (true) { const [y, x] = path[path.length - 1]; // 자리에 설 때마다(돌아왔을 때도) 위쪽부터 다시 살핀다 — 그사이 얻은 열쇠로 열리는 문이 있을 수 있다 const step = STEPS.find(([dy, dx]) => canEnter(y + dy, x + dx)); if (step !== undefined) { const ny = y + step[0], nx = x + step[1]; visited[ny][nx] = true; const ch = grid[ny][nx]; if (isLower(ch) && !keys.has(ch)) { keys.add(ch); picked += ch; } path.push([ny, nx]); } else { if (path.length === 1) break; // 처음 자리에서 더 갈 곳이 없으면 멈춘다 path.pop(); // 왔던 칸으로 한 칸 되돌아간다 } log.push(path[path.length - 1]);}const moves = log.length - 1;const seen = visited.flat().filter(Boolean).length;const out = [`${moves} ${seen}`, picked || "-"];for (const t of queries) { const [y, x] = log[Math.min(t, moves)]; // 멈춘 뒤에는 처음 자리에 그대로 있다 out.push(`${y + 1} ${x + 1}`);}console.log(out.join("\n"));
JavaMain.java · 79 줄
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.ArrayList;import java.util.List;import java.util.StringTokenizer;public class Main { static int r, c; static char[][] grid; static boolean[][] visited; static boolean[] keys = new boolean[26]; static boolean canEnter(int y, int x) { if (y < 0 || y >= r || x < 0 || x >= c || visited[y][x]) return false; char ch = grid[y][x]; if (ch == '#') return false; if (Character.isUpperCase(ch)) return keys[ch - 'A']; // 문은 맞는 열쇠가 있어야 들어간다 return true; } public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(in.readLine()); r = Integer.parseInt(st.nextToken()); c = Integer.parseInt(st.nextToken()); grid = new char[r][]; int sy = 0, sx = 0; for (int y = 0; y < r; y++) { grid[y] = in.readLine().trim().toCharArray(); for (int x = 0; x < c; x++) if (grid[y][x] == 'S') { sy = y; sx = x; } } int q = Integer.parseInt(in.readLine().trim()); st = new StringTokenizer(in.readLine()); int[] dy = {-1, 0, 1, 0}, dx = {0, 1, 0, -1}; // 위, 오른쪽, 아래, 왼쪽 visited = new boolean[r][c]; visited[sy][sx] = true; StringBuilder picked = new StringBuilder(); // 새로 얻은 열쇠(얻은 차례) ArrayDeque<int[]> path = new ArrayDeque<>(); // 지금까지 들어온 길(스택): 맨 위가 지금 자리 path.push(new int[] {sy, sx}); List<int[]> log = new ArrayList<>(); // log.get(t) = t번 움직인 뒤의 자리 log.add(path.peek()); int seen = 1; while (true) { int[] cur = path.peek(); // 자리에 설 때마다(돌아왔을 때도) 위쪽부터 다시 살핀다 — 그사이 얻은 열쇠로 열리는 문이 있을 수 있다 int d = 0; while (d < 4 && !canEnter(cur[0] + dy[d], cur[1] + dx[d])) d++; if (d < 4) { int ny = cur[0] + dy[d], nx = cur[1] + dx[d]; visited[ny][nx] = true; seen++; char ch = grid[ny][nx]; if (Character.isLowerCase(ch) && !keys[ch - 'a']) { keys[ch - 'a'] = true; picked.append(ch); } path.push(new int[] {ny, nx}); } else { if (path.size() == 1) break; // 처음 자리에서 더 갈 곳이 없으면 멈춘다 path.pop(); // 왔던 칸으로 한 칸 되돌아간다 } log.add(path.peek()); } int moves = log.size() - 1; StringBuilder out = new StringBuilder(); out.append(moves).append(' ').append(seen).append('\n'); out.append(picked.length() > 0 ? picked : "-").append('\n'); for (int i = 0; i < q; i++) { int[] at = log.get(Math.min(Integer.parseInt(st.nextToken()), moves)); // 멈춘 뒤에는 처음 자리에 그대로 있다 out.append(at[0] + 1).append(' ').append(at[1] + 1).append('\n'); } System.out.print(out); }}
C#Main.cs · 75 줄
using System;using System.Collections.Generic;using System.Linq;using System.Text;class Program{ static void Main() { int[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray(); int r = first[0], c = first[1]; var grid = new string[r]; (int y, int x) start = (0, 0); for (int y = 0; y < r; y++) { grid[y] = Console.ReadLine().Trim(); int x = grid[y].IndexOf('S'); if (x >= 0) start = (y, x); } int q = int.Parse(Console.ReadLine().Trim()); int[] queries = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries).Select(int.Parse).ToArray(); (int dy, int dx)[] steps = { (-1, 0), (0, 1), (1, 0), (0, -1) }; // 위, 오른쪽, 아래, 왼쪽 var visited = new bool[r, c]; visited[start.y, start.x] = true; var keys = new HashSet<char>(); var picked = new StringBuilder(); // 새로 얻은 열쇠(얻은 차례) var path = new Stack<(int y, int x)>(); // 지금까지 들어온 길(스택): 맨 위가 지금 자리 path.Push(start); var log = new List<(int y, int x)> { start }; // log[t] = t번 움직인 뒤의 자리 int seen = 1; bool CanEnter(int y, int x) { if (y < 0 || y >= r || x < 0 || x >= c || visited[y, x]) return false; char ch = grid[y][x]; if (ch == '#') return false; if (char.IsUpper(ch)) return keys.Contains(char.ToLower(ch)); // 문은 맞는 열쇠가 있어야 들어간다 return true; } while (true) { var (y, x) = path.Peek(); // 자리에 설 때마다(돌아왔을 때도) 위쪽부터 다시 살핀다 — 그사이 얻은 열쇠로 열리는 문이 있을 수 있다 int d = Array.FindIndex(steps, s => CanEnter(y + s.dy, x + s.dx)); if (d >= 0) { int ny = y + steps[d].dy, nx = x + steps[d].dx; visited[ny, nx] = true; seen++; char ch = grid[ny][nx]; if (char.IsLower(ch) && keys.Add(ch)) picked.Append(ch); // Add는 새로 넣었을 때만 true path.Push((ny, nx)); } else { if (path.Count == 1) break; // 처음 자리에서 더 갈 곳이 없으면 멈춘다 path.Pop(); // 왔던 칸으로 한 칸 되돌아간다 } log.Add(path.Peek()); } int moves = log.Count - 1; var out_ = new StringBuilder(); out_.Append(moves).Append(' ').Append(seen).Append('\n'); out_.Append(picked.Length > 0 ? picked.ToString() : "-").Append('\n'); foreach (int t in queries) { var (y, x) = log[Math.Min(t, moves)]; // 멈춘 뒤에는 처음 자리에 그대로 있다 out_.Append(y + 1).Append(' ').Append(x + 1).Append('\n'); } Console.Write(out_); }}
C++main.cpp · 66 줄
#include <algorithm>#include <array>#include <cctype>#include <iostream>#include <string>#include <utility>#include <vector>int main() { int r, c; std::cin >> r >> c; std::vector<std::string> grid(r); std::pair<int, int> start{0, 0}; for (int y = 0; y < r; y++) { std::cin >> grid[y]; if (auto x = grid[y].find('S'); x != std::string::npos) start = {y, static_cast<int>(x)}; } const std::array<std::pair<int, int>, 4> STEPS{{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}}; // 위, 오른쪽, 아래, 왼쪽 std::vector<std::vector<bool>> visited(r, std::vector<bool>(c, false)); std::array<bool, 26> keys{}; std::string picked; // 새로 얻은 열쇠(얻은 차례) std::vector<std::pair<int, int>> path{start}; // 지금까지 들어온 길(스택): 맨 끝이 지금 자리 std::vector<std::pair<int, int>> log{start}; // log[t] = t번 움직인 뒤의 자리 visited[start.first][start.second] = true; int seen = 1; auto canEnter = [&](int y, int x) { if (y < 0 || y >= r || x < 0 || x >= c || visited[y][x]) return false; char ch = grid[y][x]; if (ch == '#') return false; if (std::isupper(static_cast<unsigned char>(ch))) return keys[ch - 'A']; // 문은 맞는 열쇠가 있어야 들어간다 return true; }; while (true) { auto [y, x] = path.back(); // 자리에 설 때마다(돌아왔을 때도) 위쪽부터 다시 살핀다 — 그사이 얻은 열쇠로 열리는 문이 있을 수 있다 auto it = std::find_if(STEPS.begin(), STEPS.end(), [&](const auto& s) { return canEnter(y + s.first, x + s.second); }); if (it != STEPS.end()) { int ny = y + it->first, nx = x + it->second; visited[ny][nx] = true; seen++; char ch = grid[ny][nx]; if (std::islower(static_cast<unsigned char>(ch)) && !keys[ch - 'a']) { keys[ch - 'a'] = true; picked += ch; } path.emplace_back(ny, nx); } else { if (path.size() == 1) break; // 처음 자리에서 더 갈 곳이 없으면 멈춘다 path.pop_back(); // 왔던 칸으로 한 칸 되돌아간다 } log.push_back(path.back()); } int moves = static_cast<int>(log.size()) - 1; std::cout << moves << " " << seen << "\n" << (picked.empty() ? "-" : picked) << "\n"; int q; std::cin >> q; for (int i = 0; i < q; i++) { int t; std::cin >> t; auto [y, x] = log[std::min(t, moves)]; // 멈춘 뒤에는 처음 자리에 그대로 있다 std::cout << y + 1 << " " << x + 1 << "\n"; }}
Cmain.c · 66 줄
#include <ctype.h>#include <stdio.h>#define MAXN 50static char grid[MAXN][MAXN + 2];static int visited[MAXN][MAXN];static int keys[26];static int r, c;static int path[MAXN * MAXN]; /* 지금까지 들어온 길(스택): 칸 번호 y * c + x */static int logCell[2 * MAXN * MAXN]; /* logCell[t] = t번 움직인 뒤의 자리 */static int canEnter(int y, int x) { if (y < 0 || y >= r || x < 0 || x >= c || visited[y][x]) return 0; char ch = grid[y][x]; if (ch == '#') return 0; if (isupper((unsigned char)ch)) return keys[ch - 'A']; /* 문은 맞는 열쇠가 있어야 들어간다 */ return 1;}int main(void) { int q, start = 0; scanf("%d %d", &r, &c); for (int y = 0; y < r; y++) { scanf("%51s", grid[y]); for (int x = 0; x < c; x++) if (grid[y][x] == 'S') start = y * c + x; } const int DY[4] = {-1, 0, 1, 0}, DX[4] = {0, 1, 0, -1}; /* 위, 오른쪽, 아래, 왼쪽 */ char picked[27]; int npicked = 0, top = 0, moves = 0, seen = 1; visited[start / c][start % c] = 1; path[top++] = start; logCell[0] = start; for (;;) { int y = path[top - 1] / c, x = path[top - 1] % c; /* 자리에 설 때마다(돌아왔을 때도) 위쪽부터 다시 살핀다 — 그사이 얻은 열쇠로 열리는 문이 있을 수 있다 */ int d = 0; while (d < 4 && !canEnter(y + DY[d], x + DX[d])) d++; if (d < 4) { int ny = y + DY[d], nx = x + DX[d]; visited[ny][nx] = 1; seen++; char ch = grid[ny][nx]; if (islower((unsigned char)ch) && !keys[ch - 'a']) { keys[ch - 'a'] = 1; picked[npicked++] = ch; } path[top++] = ny * c + nx; } else { if (top == 1) break; /* 처음 자리에서 더 갈 곳이 없으면 멈춘다 */ top--; /* 왔던 칸으로 한 칸 되돌아간다 */ } logCell[++moves] = path[top - 1]; } picked[npicked] = '\0'; printf("%d %d\n%s\n", moves, seen, npicked > 0 ? picked : "-"); scanf("%d", &q); for (int i = 0; i < q; i++) { int t; scanf("%d", &t); int at = logCell[t < moves ? t : moves]; /* 멈춘 뒤에는 처음 자리에 그대로 있다 */ printf("%d %d\n", at / c + 1, at % c + 1); } return 0;}
Craykonmain.cray · 104 줄
첫줄 = 콘솔.수들읽기();r = 첫줄[0];c = 첫줄[1];grid = [];start = 0; // 칸은 수 하나(y * c + x)로 다룬다반복 (y = 0; y < r; y++){ 줄 = 콘솔.줄읽기().공백제거(); grid.넣기(줄); x = 줄.자리찾기("S"); 만약 (x >= 0) { start = y * c + x; }}q = 콘솔.줄읽기().공백제거().수로변환();queries = 콘솔.수들읽기();DY = [-1, 0, 1, 0]; // 위, 오른쪽, 아래, 왼쪽DX = [0, 1, 0, -1];visited = 새목록(r * c, 거짓);visited[start] = 참;keys = 사전();picked = ""; // 새로 얻은 열쇠(얻은 차례)대문자인가(ch){ 돌려주기 ch >= "A" && ch <= "Z";}소문자인가(ch){ 돌려주기 ch >= "a" && ch <= "z";}들어갈수있나(y, x){ 만약 (y < 0 || y >= r || x < 0 || x >= c) { 돌려주기 거짓; } 만약 (visited[y * c + x]) { 돌려주기 거짓; } ch = grid[y][x]; 만약 (ch == "#") { 돌려주기 거짓; } 만약 (대문자인가(ch)) { 돌려주기 keys.있나(ch.소문자로변환()); // 문은 맞는 열쇠가 있어야 들어간다 } 돌려주기 참;}path = [start]; // 지금까지 들어온 길(스택): 맨 끝이 지금 자리log = [start]; // log[t] = t번 움직인 뒤의 자리seen = 1;동안 (참){ cell = path[path.개수 - 1]; y = 수학.몫(cell, c); x = cell % c; // 자리에 설 때마다(돌아왔을 때도) 위쪽부터 다시 살핀다 — 그사이 얻은 열쇠로 열리는 문이 있을 수 있다 d = 0; 동안 (d < 4 && !들어갈수있나(y + DY[d], x + DX[d])) { d += 1; } 만약 (d < 4) { ny = y + DY[d]; nx = x + DX[d]; visited[ny * c + nx] = 참; seen += 1; ch = grid[ny][nx]; 만약 (소문자인가(ch) && !keys.있나(ch)) { keys[ch] = 참; picked = picked + ch; } path.넣기(ny * c + nx); } 아니면 { 만약 (path.개수 == 1) { 그만; // 처음 자리에서 더 갈 곳이 없으면 멈춘다 } path.자리빼기(path.개수 - 1); // 왔던 칸으로 한 칸 되돌아간다 } log.넣기(path[path.개수 - 1]);}moves = log.개수 - 1;콘솔.쓰기(moves + " " + seen);콘솔.쓰기(picked.길이 > 0 ? picked : "-");각각 (t 에서 queries){ at = log[수학.작은수(t, moves)]; // 멈춘 뒤에는 처음 자리에 그대로 있다 콘솔.쓰기(수학.몫(at, c) + 1 + " " + (at % c + 1));}