R줄 C칸짜리 지도가 주어진다.
'.'은 빈칸이고 '#'은 벽이다.
왼쪽 위 칸에서 출발해 오른쪽 아래 칸까지 가려 한다.
두 칸은 언제나 빈칸이다.
한 번 움직이면 위·아래·왼쪽·오른쪽으로 맞닿은 한 칸으로 간다(지도 밖으로는 못 나간다).
벽 칸으로는 그 벽을 부수고 들어갈 수 있는데, 길 전체에서 부술 수 있는 벽은 모두 K개까지이다.
한 번 부순 벽 칸은 빈칸이 되어, 다시 지나가도 또 부수지 않는다.
벽을 부수고 들어가는 것도 한 번 움직인 것으로 센다.
오른쪽 아래 칸까지 가는 가장 적은 이동 횟수를 출력하라.
갈 수 없으면 -1을 출력하고, 지도가 한 칸짜리이면 0을 출력한다.
입력
첫 줄에 R, C, K가 주어지고, 다음 R줄에 '.'과 '#'로만 된 길이 C인 문자열이 주어진다. 1 ≤ R, C ≤ 30, 0 ≤ K ≤ 10. 왼쪽 위 칸과 오른쪽 아래 칸은 '.'이다.
출력
가장 적은 이동 횟수 또는 -1
예시 1 · stdin
4 5 1
...#.
##.#.
...#.
.###.
stdout
7
예시 2 · stdin
4 5 0
...#.
##.#.
...#.
.###.
stdout
-1
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
가장 적은 이동 횟수는 너비 우선 탐색(BFS): 큐로 가까운 곳부터 퍼지면 도착 칸에 처음 닿을 때가 답이에요. 큐 대신 스택으로 돌면(깊이 우선) 처음 닿은 길이 돌아가는 길일 수 있어요. 이 문제의 핵심은 상태예요: 같은 칸이라도 벽을 2개 부수고 온 것과 0개 부수고 온 것은 앞으로 갈 수 있는 곳이 달라요. 그래서 '가 본 곳' 표시를 칸이 아니라 (칸, 부순 벽 수)마다 해요 — 칸에만 표시하면 벽을 부수고 먼저 온 길이 그 칸을 차지해서, 덜 부수고 조금 늦게 온 길이 막혀요(가장 흔한 함정). 상태는 많아야 30 × 30 × 11 = 9,900개라 상태마다 한 번씩만 넣으면 빨라요. 벽에 들어갈 때는 '들어간 뒤 부순 수 ≤ K'를 봐야 해요; '들어가기 전 부순 수 ≤ K'로 보면 K + 1개를 부숴요. 상태를 담는 법도 언어마다 달라요: Python은 3차원 목록 [[[-1] * (k + 1) for _ in range(c)] for _ in range(r)]와 deque의 튜플, Java int[r][c][k + 1](만들면 0이라 Arrays.fill로 -1을 채워요)과 ArrayDeque<int[]>, C# new int[r, c, k + 1](직사각형 3차원 배열)과 이름 붙은 튜플 Queue<(int y, int x, int used)>, C++ std::vector 세 겹과 std::queue<std::tuple<int, int, int>>(구조적 바인딩 auto [y, x, used]로 꺼내요). C·JavaScript·TypeScript·크레이콘은 상태를 수 하나 (y * c + x) * (k + 1) + used로 펴서 1차원 배열 하나에 담고, 큐는 목록 끝에 넣기만 하고 앞 자리(head)를 옮기며 꺼내요(C·크레이콘은 큐에도 그 수를, JavaScript·TypeScript는 [y, x, used]를 넣어요). 크레이콘 목록은 10,000칸까지라, 상태 수가 많아야 9,900이 되도록 범위를 정했어요. 크레이콘에서 상태를 다시 나눌 때는 /가 소수까지 나누니 수학.몫(s, k + 1)과 %를 써요.
Pythonmain.py · 25 줄
from collections import dequer, c, k = map(int, input().split())grid = [input().strip() for _ in range(r)]# 상태 = (칸, 지금까지 부순 벽 수). 같은 칸이라도 부순 수가 다르면 다른 상태다# dist[y][x][used] = 그 상태까지 가장 적은 이동 횟수(-1은 아직 못 감)dist = [[[-1] * (k + 1) for _ in range(c)] for _ in range(r)]dist[0][0][0] = 0queue = deque([(0, 0, 0)])answer = -1while queue: y, x, used = queue.popleft() if (y, x) == (r - 1, c - 1): answer = dist[y][x][used] # 너비 우선 탐색(BFS)이라 처음 닿을 때가 가장 짧다 break for dy, dx in ((1, 0), (-1, 0), (0, 1), (0, -1)): ny, nx = y + dy, x + dx if not (0 <= ny < r and 0 <= nx < c): continue nused = used + (1 if grid[ny][nx] == "#" else 0) if nused <= k and dist[ny][nx][nused] == -1: dist[ny][nx][nused] = dist[y][x][used] + 1 queue.append((ny, nx, nused))print(answer)
JavaScriptmain.js · 28 줄
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [r, c, k] = lines[0].trim().split(/\s+/).map(Number);const grid = lines.slice(1, 1 + r).map((s) => s.trim());const STEPS = [[1, 0], [-1, 0], [0, 1], [0, -1]];// 상태 = (칸, 지금까지 부순 벽 수)를 수 하나로: (y * c + x) * (k + 1) + usedconst id = (y, x, used) => (y * c + x) * (k + 1) + used;const dist = new Array(r * c * (k + 1)).fill(-1);dist[id(0, 0, 0)] = 0;const queue = [[0, 0, 0]];let answer = -1;for (let head = 0; head < queue.length; head++) { const [y, x, used] = queue[head]; if (y === r - 1 && x === c - 1) { answer = dist[id(y, x, used)]; // 너비 우선 탐색(BFS)이라 처음 닿을 때가 가장 짧다 break; } for (const [dy, dx] of STEPS) { const ny = y + dy, nx = x + dx; if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue; const nused = used + (grid[ny][nx] === "#" ? 1 : 0); if (nused <= k && dist[id(ny, nx, nused)] === -1) { dist[id(ny, nx, nused)] = dist[id(y, x, used)] + 1; queue.push([ny, nx, nused]); } }}console.log(answer);
TypeScriptmain.ts · 30 줄
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const [r, c, k]: number[] = lines[0].trim().split(/\s+/).map(Number);const grid: string[] = lines.slice(1, 1 + r).map((s) => s.trim());const STEPS: [number, number][] = [[1, 0], [-1, 0], [0, 1], [0, -1]];// 상태 = (칸, 지금까지 부순 벽 수)를 수 하나로: (y * c + x) * (k + 1) + usedconst id = (y: number, x: number, used: number): number => (y * c + x) * (k + 1) + used;const dist: number[] = new Array<number>(r * c * (k + 1)).fill(-1);dist[id(0, 0, 0)] = 0;const queue: [number, number, number][] = [[0, 0, 0]];let answer = -1;for (let head = 0; head < queue.length; head++) { const [y, x, used] = queue[head]; if (y === r - 1 && x === c - 1) { answer = dist[id(y, x, used)]; // 너비 우선 탐색(BFS)이라 처음 닿을 때가 가장 짧다 break; } for (const [dy, dx] of STEPS) { const ny = y + dy, nx = x + dx; if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue; const nused = used + (grid[ny][nx] === "#" ? 1 : 0); if (nused <= k && dist[id(ny, nx, nused)] === -1) { dist[id(ny, nx, nused)] = dist[id(y, x, used)] + 1; queue.push([ny, nx, nused]); } }}console.log(answer);
JavaMain.java · 45 줄
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;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 r = Integer.parseInt(st.nextToken()); int c = Integer.parseInt(st.nextToken()); int k = Integer.parseInt(st.nextToken()); String[] grid = new String[r]; for (int y = 0; y < r; y++) grid[y] = in.readLine().trim(); int[] dy = {1, -1, 0, 0}, dx = {0, 0, 1, -1}; // 상태 = (칸, 지금까지 부순 벽 수). 같은 칸이라도 부순 수가 다르면 다른 상태다 int[][][] dist = new int[r][c][k + 1]; for (int[][] plane : dist) for (int[] cell : plane) java.util.Arrays.fill(cell, -1); dist[0][0][0] = 0; ArrayDeque<int[]> queue = new ArrayDeque<>(); queue.addLast(new int[] {0, 0, 0}); int answer = -1; while (!queue.isEmpty()) { int[] cur = queue.pollFirst(); int y = cur[0], x = cur[1], used = cur[2]; if (y == r - 1 && x == c - 1) { answer = dist[y][x][used]; // 너비 우선 탐색(BFS)이라 처음 닿을 때가 가장 짧다 break; } for (int d = 0; d < 4; d++) { int ny = y + dy[d], nx = x + dx[d]; if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue; int nused = used + (grid[ny].charAt(nx) == '#' ? 1 : 0); if (nused <= k && dist[ny][nx][nused] == -1) { dist[ny][nx][nused] = dist[y][x][used] + 1; queue.addLast(new int[] {ny, nx, nused}); } } } System.out.println(answer); }}
C#Main.cs · 47 줄
using System;using System.Collections.Generic;class Program{ static void Main() { string[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); int r = int.Parse(first[0]); int c = int.Parse(first[1]); int k = int.Parse(first[2]); var grid = new string[r]; for (int y = 0; y < r; y++) grid[y] = Console.ReadLine().Trim(); int[] dy = { 1, -1, 0, 0 }, dx = { 0, 0, 1, -1 }; // 상태 = (칸, 지금까지 부순 벽 수). 같은 칸이라도 부순 수가 다르면 다른 상태다 var dist = new int[r, c, k + 1]; for (int y = 0; y < r; y++) for (int x = 0; x < c; x++) for (int u = 0; u <= k; u++) dist[y, x, u] = -1; dist[0, 0, 0] = 0; var queue = new Queue<(int y, int x, int used)>(); queue.Enqueue((0, 0, 0)); int answer = -1; while (queue.Count > 0) { var (cy, cx, used) = queue.Dequeue(); if (cy == r - 1 && cx == c - 1) { answer = dist[cy, cx, used]; // 너비 우선 탐색(BFS)이라 처음 닿을 때가 가장 짧다 break; } for (int d = 0; d < 4; d++) { int ny = cy + dy[d], nx = cx + dx[d]; if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue; int nused = used + (grid[ny][nx] == '#' ? 1 : 0); if (nused <= k && dist[ny, nx, nused] == -1) { dist[ny, nx, nused] = dist[cy, cx, used] + 1; queue.Enqueue((ny, nx, nused)); } } } Console.WriteLine(answer); }}
C++main.cpp · 38 줄
#include <iostream>#include <queue>#include <string>#include <tuple>#include <vector>int main() { int r, c, k; std::cin >> r >> c >> k; std::vector<std::string> grid(r); for (auto& row : grid) std::cin >> row; const int DY[4] = {1, -1, 0, 0}, DX[4] = {0, 0, 1, -1}; // 상태 = (칸, 지금까지 부순 벽 수). 같은 칸이라도 부순 수가 다르면 다른 상태다 std::vector<std::vector<std::vector<int>>> dist(r, std::vector<std::vector<int>>(c, std::vector<int>(k + 1, -1))); std::queue<std::tuple<int, int, int>> q; dist[0][0][0] = 0; q.push({0, 0, 0}); int answer = -1; while (!q.empty()) { auto [y, x, used] = q.front(); q.pop(); if (y == r - 1 && x == c - 1) { answer = dist[y][x][used]; // 너비 우선 탐색(BFS)이라 처음 닿을 때가 가장 짧다 break; } for (int d = 0; d < 4; d++) { int ny = y + DY[d], nx = x + DX[d]; if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue; int nused = used + (grid[ny][nx] == '#' ? 1 : 0); if (nused <= k && dist[ny][nx][nused] == -1) { dist[ny][nx][nused] = dist[y][x][used] + 1; q.push({ny, nx, nused}); } } } std::cout << answer << "\n";}
Cmain.c · 42 줄
#include <stdio.h>#define MAXS (30 * 30 * 11)static char grid[30][32];static int dist[MAXS];static int queue[MAXS]; /* 상태마다 한 번만 넣으니 상태 수만큼이면 된다 */int main(void) { int r, c, k; scanf("%d %d %d", &r, &c, &k); for (int y = 0; y < r; y++) scanf("%31s", grid[y]); const int DY[4] = {1, -1, 0, 0}, DX[4] = {0, 0, 1, -1}; /* 상태 = (칸, 지금까지 부순 벽 수)를 수 하나로: (y * c + x) * (k + 1) + used */ int states = r * c * (k + 1); for (int s = 0; s < states; s++) dist[s] = -1; int head = 0, tail = 0, answer = -1; dist[0] = 0; queue[tail++] = 0; while (head < tail) { int s = queue[head++]; int used = s % (k + 1), cell = s / (k + 1); int y = cell / c, x = cell % c; if (y == r - 1 && x == c - 1) { answer = dist[s]; /* 너비 우선 탐색(BFS)이라 처음 닿을 때가 가장 짧다 */ break; } for (int d = 0; d < 4; d++) { int ny = y + DY[d], nx = x + DX[d]; if (ny < 0 || ny >= r || nx < 0 || nx >= c) continue; int nused = used + (grid[ny][nx] == '#'); int ns = (ny * c + nx) * (k + 1) + nused; if (nused <= k && dist[ns] == -1) { dist[ns] = dist[s] + 1; queue[tail++] = ns; } } } printf("%d\n", answer); return 0;}
Craykonmain.cray · 55 줄
첫줄 = 콘솔.수들읽기();r = 첫줄[0];c = 첫줄[1];k = 첫줄[2];grid = [];반복 (i = 0; i < r; i++){ grid.넣기(콘솔.줄읽기().공백제거());}DY = [1, -1, 0, 0];DX = [0, 0, 1, -1];// 상태 = (칸, 지금까지 부순 벽 수)를 수 하나로: (y * c + x) * (k + 1) + used// 상태는 많아야 30 × 30 × 11 = 9,900개라 목록 하나(10,000칸까지)에 들어간다dist = 새목록(r * c * (k + 1), -1);dist[0] = 0;queue = [0];head = 0;answer = -1;동안 (head < queue.개수 && answer == -1){ s = queue[head]; head += 1; used = s % (k + 1); cell = 수학.몫(s, k + 1); y = 수학.몫(cell, c); x = cell % c; 만약 (y == r - 1 && x == c - 1) { answer = dist[s]; // 너비 우선 탐색(BFS)이라 처음 닿을 때가 가장 짧다 } 아니면 { 반복 (d = 0; d < 4; d++) { ny = y + DY[d]; nx = x + DX[d]; 만약 (ny >= 0 && ny < r && nx >= 0 && nx < c) { nused = used; 만약 (grid[ny][nx] == "#") { nused += 1; } ns = (ny * c + nx) * (k + 1) + nused; 만약 (nused <= k && dist[ns] == -1) { dist[ns] = dist[s] + 1; queue.넣기(ns); } } } }}콘솔.쓰기(answer);