겨울 아침, H줄 W칸짜리 교실에 난로가 하나 있다.
지도에서 '.'은 바닥 칸, '#'은 책장이 놓인 칸, 'S'는 난로가 놓인 칸이다.
0분에는 난로가 놓인 칸만 따뜻하다.
1분이 지날 때마다, 따뜻한 칸과 위·아래·왼쪽·오른쪽으로 맞닿은 바닥 칸이 새로 따뜻해진다.
책장이 놓인 칸은 따뜻해지지 않고, 온기는 책장을 지나가지 못한다.
온기는 교실 밖으로 나가지 않는다. 맨 윗줄의 위와 맨 아랫줄의 아래, 맨 왼쪽 칸의 왼쪽과 맨 오른쪽 칸의 오른쪽에는 아무 칸도 없다.
한 번 따뜻해진 칸은 계속 따뜻하다.
새로 따뜻해진 칸이 있는 마지막 시각을 T분이라 하자. 난로 칸 말고 따뜻해지는 칸이 없으면 T는 0이다.
첫 줄에 T를 출력하라.
둘째 줄에 0분, 1분, …, T분에 새로 따뜻해진 칸의 수를 차례대로 빈칸 하나로 띄워 출력하라. 0분의 값은 난로 칸 하나라서 언제나 1이다.
셋째 줄에 끝까지 따뜻해지지 않는 바닥 칸의 수를 출력하라.
입력
첫 줄에 H와 W가 빈칸 하나로 나뉘어 주어진다. 다음 H줄에 교실 지도가 한 줄씩 주어지고, 줄마다 '.', '#', 'S'로만 된 길이 W인 문자열이다. 1 ≤ H ≤ 20, 1 ≤ W ≤ 20. 'S'는 지도 전체에 꼭 하나 있다
출력
세 줄. 첫 줄에 T, 둘째 줄에 0분부터 T분까지 새로 따뜻해진 칸의 수 T + 1개, 셋째 줄에 끝까지 따뜻해지지 않는 바닥 칸의 수
예시 1 · stdin
4 5
S..#.
.#.##
....#
...#.
stdout
5
1 2 2 3 2 2
2
예시 2 · stdin
1 4
.S#.
stdout
1
1 1
1
main.py
오류 목록00F8 ↓ · ⇧F8 ↑
입력(stdin)
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
다른 언어로는?언어별 풀이 보기 · 8개 언어 풀이
난로 칸을 큐에 넣고, 앞에서 하나씩 꺼내며 네 이웃을 살펴서 처음 닿은 칸에 '꺼낸 칸의 시각 + 1'을 적고 큐 뒤에 넣어요. 네 방향은 dr = [-1, 1, 0, 0], dc = [0, 0, -1, 1] 두 배열로 두면 반복문 하나로 돌 수 있어요. 큐는 Python deque(popleft), Java ArrayDeque(pollFirst), C# Queue<T>(Dequeue), C++ std::queue(front로 보고 pop으로 뺌)를 쓰고, JS·TS·C·크레이콘은 배열 뒤에 넣으면서 '맨 앞 자리' 번호 하나만 뒤로 옮겨요. 언어마다 가장 크게 갈리는 곳은 교실 밖 칸을 읽었을 때예요. 함정 하나: 0 <= nr을 빼고 nr < H만 물으면 Python은 멈추지 않아요. grid[-1]이 맨 끝 줄이라서 온기가 벽을 뚫고 반대편으로 넘어가요. 예시 2에서 난로 왼쪽 칸의 왼쪽이 맨 오른쪽 칸으로 읽혀서 2와 1 1 1, 0이 나오고, 예시 1은 1 4 4 3 1 1과 0이 돼요. JS·TS는 grid[-1]이 undefined라서 그다음 [nc]에서 TypeError로 멈추고, 크레이콘도 '목록에는 0~3번만 있어요'라는 오류로 멈춰요. Java와 C#도 예외로 멈추지만, C와 C++의 []는 범위를 확인하지 않아요. 배열 밖을 읽으면 무슨 일이 일어날지 정해져 있지 않아요(정의되지 않은 동작). 그래서 여덟 풀이 모두 지도를 읽기 전에 네 가지 범위를 먼저 물어요. 함정 둘: '따뜻해졌다'는 표시를 큐에 넣을 때가 아니라 꺼낼 때 하면, 두 이웃에게서 같은 분에 온기를 받는 칸이 큐에 두 번 들어가 두 번 세어져요. 예시 1의 둘째 줄이 1 2 2 3 4 3이 돼요. 함정 셋: 맨 뒤에서 꺼내면(JS pop()) 큐가 아니라 스택이 되어 가까운 칸보다 먼 칸으로 먼저 파고들어요. 예시 1이 7과 1 2 1 1 1 3 2 1이 돼요. JS의 shift()도 맨 앞에서 꺼내 줘요. 칸이 많아야 400개인 이 문제에서는 차이가 없지만, 채점 서버의 Node 22에서 재어 보니 200,000개를 넣고 shift()로 모두 꺼내는 데 3초쯤 걸렸고 자리 번호를 옮기는 쪽은 0.01초도 걸리지 않았어요.
Pythonmain.py · 33 줄
import sysfrom collections import dequelines = sys.stdin.read().split("\n")H, W = map(int, lines[0].split())grid = lines[1:1 + H]minute = [[-1] * W for _ in range(H)] # minute[r][c] = 따뜻해진 시각, 아직이면 -1queue = deque()for r in range(H): for c in range(W): if grid[r][c] == "S": minute[r][c] = 0 queue.append((r, c))counts = [1] # counts[t] = t분에 새로 따뜻해진 칸의 수while queue: r, c = queue.popleft() # 먼저 따뜻해진 칸부터 꺼낸다 for dr, dc in ((-1, 0), (1, 0), (0, -1), (0, 1)): nr, nc = r + dr, c + dc # 교실 밖인지 먼저 묻는다. Python의 grid[-1]은 오류가 아니라 맨 끝 줄이다 if 0 <= nr < H and 0 <= nc < W and grid[nr][nc] != "#" and minute[nr][nc] == -1: t = minute[r][c] + 1 minute[nr][nc] = t # 큐에 넣을 때 바로 표시해야 같은 칸이 두 번 들어가지 않는다 if t == len(counts): counts.append(0) counts[t] += 1 queue.append((nr, nc))cold = sum(1 for r in range(H) for c in range(W) if grid[r][c] == "." and minute[r][c] == -1)print(len(counts) - 1)print(" ".join(map(str, counts)))print(cold)
JavaScriptmain.js · 46 줄
const lines = require("fs").readFileSync(0, "utf8").split("\n");const [H, W] = lines[0].trim().split(" ").map(Number);const grid = lines.slice(1, 1 + H);// minute[r][c] = 따뜻해진 시각, 아직이면 -1const minute = Array.from({ length: H }, () => new Array(W).fill(-1));// JS에는 큐가 따로 없다. 배열 뒤에 넣고, 맨 앞 자리(head)만 뒤로 옮긴다const queue = [];let head = 0;for (let r = 0; r < H; r++) { for (let c = 0; c < W; c++) { if (grid[r][c] === "S") { minute[r][c] = 0; queue.push([r, c]); } }}const counts = [1]; // counts[t] = t분에 새로 따뜻해진 칸의 수const dr = [-1, 1, 0, 0];const dc = [0, 0, -1, 1];while (head < queue.length) { const [r, c] = queue[head++]; // 먼저 따뜻해진 칸부터 꺼낸다 for (let d = 0; d < 4; d++) { const nr = r + dr[d]; const nc = c + dc[d]; // 교실 밖인지 먼저 묻는다. grid[-1]은 undefined라서 그 뒤의 [nc]에서 오류가 난다 if (nr < 0 || nr >= H || nc < 0 || nc >= W) continue; if (grid[nr][nc] === "#" || minute[nr][nc] !== -1) continue; const t = minute[r][c] + 1; minute[nr][nc] = t; // 큐에 넣을 때 바로 표시해야 같은 칸이 두 번 들어가지 않는다 if (t === counts.length) counts.push(0); counts[t]++; queue.push([nr, nc]); }}let cold = 0;for (let r = 0; r < H; r++) { for (let c = 0; c < W; c++) { if (grid[r][c] === "." && minute[r][c] === -1) cold++; }}console.log(counts.length - 1);console.log(counts.join(" "));console.log(cold);
TypeScriptmain.ts · 48 줄
import { readFileSync } from "node:fs";const lines: string[] = readFileSync(0, "utf8").split("\n");const [H, W]: number[] = lines[0].trim().split(" ").map(Number);const grid: string[] = lines.slice(1, 1 + H);// minute[r][c] = 따뜻해진 시각, 아직이면 -1const minute: number[][] = Array.from({ length: H }, (): number[] => new Array<number>(W).fill(-1));// TS에도 큐가 따로 없다. 배열 뒤에 넣고, 맨 앞 자리(head)만 뒤로 옮긴다const queue: [number, number][] = [];let head = 0;for (let r = 0; r < H; r++) { for (let c = 0; c < W; c++) { if (grid[r][c] === "S") { minute[r][c] = 0; queue.push([r, c]); } }}const counts: number[] = [1]; // counts[t] = t분에 새로 따뜻해진 칸의 수const dr: number[] = [-1, 1, 0, 0];const dc: number[] = [0, 0, -1, 1];while (head < queue.length) { const [r, c] = queue[head++]; // 먼저 따뜻해진 칸부터 꺼낸다 for (let d = 0; d < 4; d++) { const nr = r + dr[d]; const nc = c + dc[d]; // 교실 밖인지 먼저 묻는다. grid[-1]은 undefined라서 그 뒤의 [nc]에서 오류가 난다 if (nr < 0 || nr >= H || nc < 0 || nc >= W) continue; if (grid[nr][nc] === "#" || minute[nr][nc] !== -1) continue; const t = minute[r][c] + 1; minute[nr][nc] = t; // 큐에 넣을 때 바로 표시해야 같은 칸이 두 번 들어가지 않는다 if (t === counts.length) counts.push(0); counts[t]++; queue.push([nr, nc]); }}let cold = 0;for (let r = 0; r < H; r++) { for (let c = 0; c < W; c++) { if (grid[r][c] === "." && minute[r][c] === -1) cold++; }}console.log(counts.length - 1);console.log(counts.join(" "));console.log(cold);
JavaMain.java · 64 줄
import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.Arrays;public class Main { public static void main(String[] args) throws IOException { BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String[] first = in.readLine().trim().split(" "); int H = Integer.parseInt(first[0]); int W = Integer.parseInt(first[1]); char[][] grid = new char[H][]; int[][] minute = new int[H][W]; // minute[r][c] = 따뜻해진 시각, 아직이면 -1 ArrayDeque<int[]> queue = new ArrayDeque<>(); for (int r = 0; r < H; r++) { grid[r] = in.readLine().trim().toCharArray(); Arrays.fill(minute[r], -1); for (int c = 0; c < W; c++) { if (grid[r][c] == 'S') { minute[r][c] = 0; queue.addLast(new int[] {r, c}); } } } int[] counts = new int[H * W]; // counts[t] = t분에 새로 따뜻해진 칸의 수 counts[0] = 1; int last = 0; // 마지막으로 새 칸이 따뜻해진 시각 int[] dr = {-1, 1, 0, 0}; int[] dc = {0, 0, -1, 1}; while (!queue.isEmpty()) { int[] cell = queue.pollFirst(); // 먼저 따뜻해진 칸부터 꺼낸다 int r = cell[0], c = cell[1]; for (int d = 0; d < 4; d++) { int nr = r + dr[d]; int nc = c + dc[d]; // 교실 밖인지 먼저 묻는다. 묻지 않으면 ArrayIndexOutOfBoundsException으로 멈춘다 if (nr < 0 || nr >= H || nc < 0 || nc >= W) continue; if (grid[nr][nc] == '#' || minute[nr][nc] != -1) continue; int t = minute[r][c] + 1; minute[nr][nc] = t; // 큐에 넣을 때 바로 표시해야 같은 칸이 두 번 들어가지 않는다 counts[t]++; last = t; queue.addLast(new int[] {nr, nc}); } } int cold = 0; for (int r = 0; r < H; r++) { for (int c = 0; c < W; c++) { if (grid[r][c] == '.' && minute[r][c] == -1) cold++; } } StringBuilder out = new StringBuilder(); out.append(last).append('\n'); for (int t = 0; t <= last; t++) { if (t > 0) out.append(' '); out.append(counts[t]); } out.append('\n').append(cold); System.out.println(out); }}
C#Main.cs · 61 줄
using System;using System.Collections.Generic;class Program{ static void Main() { string[] first = Console.ReadLine().Trim().Split(' '); int H = int.Parse(first[0]); int W = int.Parse(first[1]); string[] grid = new string[H]; int[,] minute = new int[H, W]; // minute[r, c] = 따뜻해진 시각, 아직이면 -1 var queue = new Queue<(int r, int c)>(); for (int r = 0; r < H; r++) { grid[r] = Console.ReadLine().Trim(); for (int c = 0; c < W; c++) { minute[r, c] = -1; if (grid[r][c] == 'S') { minute[r, c] = 0; queue.Enqueue((r, c)); } } } var counts = new List<int> { 1 }; // counts[t] = t분에 새로 따뜻해진 칸의 수 int[] dr = { -1, 1, 0, 0 }; int[] dc = { 0, 0, -1, 1 }; while (queue.Count > 0) { var (r, c) = queue.Dequeue(); // 먼저 따뜻해진 칸부터 꺼낸다 for (int d = 0; d < 4; d++) { int nr = r + dr[d]; int nc = c + dc[d]; // 교실 밖인지 먼저 묻는다. 묻지 않으면 IndexOutOfRangeException으로 멈춘다 if (nr < 0 || nr >= H || nc < 0 || nc >= W) continue; if (grid[nr][nc] == '#' || minute[nr, nc] != -1) continue; int t = minute[r, c] + 1; minute[nr, nc] = t; // 큐에 넣을 때 바로 표시해야 같은 칸이 두 번 들어가지 않는다 if (t == counts.Count) counts.Add(0); counts[t]++; queue.Enqueue((nr, nc)); } } int cold = 0; for (int r = 0; r < H; r++) { for (int c = 0; c < W; c++) { if (grid[r][c] == '.' && minute[r, c] == -1) cold++; } } Console.WriteLine(counts.Count - 1); Console.WriteLine(string.Join(" ", counts)); Console.WriteLine(cold); }}
C++main.cpp · 57 줄
#include <iostream>#include <queue>#include <string>#include <utility>#include <vector>using namespace std;int main() { int H, W; cin >> H >> W; vector<string> grid(H); vector<vector<int>> minute(H, vector<int>(W, -1)); // 따뜻해진 시각, 아직이면 -1 queue<pair<int, int>> q; for (int r = 0; r < H; r++) { cin >> grid[r]; for (int c = 0; c < W; c++) { if (grid[r][c] == 'S') { minute[r][c] = 0; q.push({r, c}); } } } vector<int> counts = {1}; // counts[t] = t분에 새로 따뜻해진 칸의 수 const int dr[4] = {-1, 1, 0, 0}; const int dc[4] = {0, 0, -1, 1}; while (!q.empty()) { auto [r, c] = q.front(); // 먼저 따뜻해진 칸부터 꺼낸다 q.pop(); // pop()은 값을 돌려주지 않는다 for (int d = 0; d < 4; d++) { int nr = r + dr[d]; int nc = c + dc[d]; // 교실 밖인지 먼저 묻는다. C++의 []는 범위를 확인하지 않고, 배열 밖을 읽으면 정의되지 않은 동작이다 if (nr < 0 || nr >= H || nc < 0 || nc >= W) continue; if (grid[nr][nc] == '#' || minute[nr][nc] != -1) continue; int t = minute[r][c] + 1; minute[nr][nc] = t; // 큐에 넣을 때 바로 표시해야 같은 칸이 두 번 들어가지 않는다 if (t == (int)counts.size()) counts.push_back(0); counts[t]++; q.push({nr, nc}); } } int cold = 0; for (int r = 0; r < H; r++) { for (int c = 0; c < W; c++) { if (grid[r][c] == '.' && minute[r][c] == -1) cold++; } } cout << counts.size() - 1 << '\n'; for (size_t t = 0; t < counts.size(); t++) { if (t > 0) cout << ' '; cout << counts[t]; } cout << '\n' << cold << '\n'; return 0;}
Cmain.c · 62 줄
#include <stdio.h>#define MAXS 20int main(void) { int H, W; static char grid[MAXS][MAXS + 1]; static int minute[MAXS][MAXS]; /* 따뜻해진 시각, 아직이면 -1 */ static int queue_r[MAXS * MAXS]; /* 배열로 만든 큐: tail 자리에 넣고 head 자리에서 꺼낸다 */ static int queue_c[MAXS * MAXS]; static int counts[MAXS * MAXS]; /* counts[t] = t분에 새로 따뜻해진 칸의 수 */ int head = 0, tail = 0, last = 0; scanf("%d %d", &H, &W); for (int r = 0; r < H; r++) { scanf("%20s", grid[r]); for (int c = 0; c < W; c++) { minute[r][c] = -1; if (grid[r][c] == 'S') { minute[r][c] = 0; queue_r[tail] = r; queue_c[tail] = c; tail++; } } } counts[0] = 1; const int dr[4] = {-1, 1, 0, 0}; const int dc[4] = {0, 0, -1, 1}; while (head < tail) { int r = queue_r[head], c = queue_c[head]; /* 먼저 따뜻해진 칸부터 꺼낸다 */ head++; for (int d = 0; d < 4; d++) { int nr = r + dr[d]; int nc = c + dc[d]; /* 교실 밖인지 먼저 묻는다. C는 범위를 확인하지 않고, 배열 밖을 읽으면 정의되지 않은 동작이다 */ if (nr < 0 || nr >= H || nc < 0 || nc >= W) continue; if (grid[nr][nc] == '#' || minute[nr][nc] != -1) continue; int t = minute[r][c] + 1; minute[nr][nc] = t; /* 큐에 넣을 때 바로 표시해야 같은 칸이 두 번 들어가지 않는다 */ counts[t]++; last = t; queue_r[tail] = nr; queue_c[tail] = nc; tail++; } } int cold = 0; for (int r = 0; r < H; r++) { for (int c = 0; c < W; c++) { if (grid[r][c] == '.' && minute[r][c] == -1) cold++; } } printf("%d\n", last); for (int t = 0; t <= last; t++) { printf(t > 0 ? " %d" : "%d", counts[t]); } printf("\n%d\n", cold); return 0;}
Craykonmain.cray · 73 줄
첫줄 = 콘솔.수들읽기();H = 첫줄[0];W = 첫줄[1];grid = [];minute = []; // minute[r][c] = 따뜻해진 시각, 아직이면 -1// 목록으로 만든 큐: 뒤에 넣고, 맨 앞 자리(head)만 뒤로 옮긴다. 줄 번호와 칸 번호를 따로 담는다queueR = [];queueC = [];head = 0;반복 (r = 0; r < H; r++){ 줄 = 콘솔.줄읽기().공백제거(); grid.넣기(줄); minute.넣기(새목록(W, -1)); 반복 (c = 0; c < W; c++) { 만약 (줄[c] == "S") { minute[r][c] = 0; queueR.넣기(r); queueC.넣기(c); } }}counts = [1]; // counts[t] = t분에 새로 따뜻해진 칸의 수dr = [-1, 1, 0, 0];dc = [0, 0, -1, 1];동안 (head < queueR.개수){ // 먼저 따뜻해진 칸부터 꺼낸다 r = queueR[head]; c = queueC[head]; head += 1; 반복 (d = 0; d < 4; d++) { nr = r + dr[d]; nc = c + dc[d]; // 교실 밖인지 먼저 묻는다. 묻지 않고 목록 밖을 읽으면 오류로 멈춘다 만약 (nr < 0 || nr >= H || nc < 0 || nc >= W) { 건너뛰기; } 만약 (grid[nr][nc] == "#" || minute[nr][nc] != -1) { 건너뛰기; } t = minute[r][c] + 1; minute[nr][nc] = t; // 큐에 넣을 때 바로 표시해야 같은 칸이 두 번 들어가지 않는다 만약 (t == counts.개수) { counts.넣기(0); } counts[t] += 1; queueR.넣기(nr); queueC.넣기(nc); }}cold = 0;반복 (r = 0; r < H; r++){ 반복 (c = 0; c < W; c++) { 만약 (grid[r][c] == "." && minute[r][c] == -1) { cold += 1; } }}콘솔.쓰기(counts.개수 - 1);콘솔.쓰기(counts.잇기(" "));콘솔.쓰기(cold);