R줄 C칸짜리 지도가 주어진다.
'#'은 땅, '.'은 물이다.
위·아래·왼쪽·오른쪽으로 맞닿은 땅은 같은 섬이다(대각선은 이어지지 않는다).
두 줄을 출력하라.
첫 줄에는 섬의 개수를 출력한다.
둘째 줄에는 왼쪽 위 칸에서 오른쪽 아래 칸까지 땅만 밟고 위·아래·왼쪽·오른쪽으로 한 칸씩 움직일 때 필요한 가장 적은 이동 횟수를 출력한다.
두 칸 중 하나라도 물이거나 갈 수 없으면 -1을 출력하고, 지도가 한 칸짜리 땅이면 0이다.
4 5 ##..# .#... .#### #...#
3 7
2 2 #. .#
2 -1
실행하면 이 줄들이 차례로 input()·표준 입력으로 들어가요(실행 중에 묻지 않아요).
$ 준비됐어요
코드를 입력해 풀려면 PC에서 열어 주세요. 모바일에서는 문제와 풀이를 볼 수 있어요.
섬 세기는 깊이 우선 탐색(DFS): 아직 안 본 땅에서 시작해 이어진 땅을 모두 표시하면 섬 하나예요.
가장 짧은 길은 너비 우선 탐색(BFS): 큐로 가까운 칸부터 퍼져 나가서 처음 닿을 때의 거리가 답이에요 — DFS로 처음 찾은 길은 돌아가는 길일 수 있어요.
DFS는 재귀로 쓰면 짧은데 깊이가 문제예요: 뱀처럼 긴 섬은 재귀가 1,300단계쯤 들어가서 Python은 기본 재귀 한도 1,000에 걸려 RecursionError가 나요 — 스택(list의 append/pop)으로 쓰거나 sys.setrecursionlimit을 올려요.
크레이콘도 재귀가 몇천 단계에서 멈춰서 목록을 스택으로 써요(넣기와 자리빼기(개수 - 1)).
C·C++·Java·C#·JavaScript는 2,500단계 재귀가 기본 스택에 들어가요.
BFS 큐: Python deque, Java ArrayDeque, C# Queue<(int, int)>, C++ std::queue<std::pair<int, int>>, C·JavaScript·크레이콘은 칸마다 한 번만 넣으니 배열과 앞 자리(head)만으로 충분해요.
2차원 표시판도 언어마다 달라요: C# new bool[r, c](직사각형 배열), Java new boolean[r][c], JavaScript는 Array.from으로 줄마다 새 배열을 만들어야 해요(new Array(r).fill([])는 모든 줄이 같은 배열이에요).
크레이콘은 y * c + x 자리로 한 목록에 담아요.
대각선으로 이으면 섬 개수가 달라지니 방향은 4개만 써요.
from collections import deque r, c = map(int, input().split())grid = [input().strip() for _ in range(r)]STEPS = ((1, 0), (-1, 0), (0, 1), (0, -1)) def neighbors(y, x): for dy, dx in STEPS: ny, nx = y + dy, x + dx if 0 <= ny < r and 0 <= nx < c and grid[ny][nx] == "#": yield ny, nx def count_islands(): """깊이 우선 탐색(DFS)을 스택으로 — 재귀는 Python 기본 깊이 1,000을 넘을 수 있다.""" seen = [[False] * c for _ in range(r)] islands = 0 for y in range(r): for x in range(c): if grid[y][x] != "#" or seen[y][x]: continue islands += 1 seen[y][x] = True stack = [(y, x)] while stack: cy, cx = stack.pop() for ny, nx in neighbors(cy, cx): if not seen[ny][nx]: seen[ny][nx] = True stack.append((ny, nx)) return islands def shortest_path(): """너비 우선 탐색(BFS): 처음 닿을 때가 가장 짧은 거리다.""" if grid[0][0] != "#" or grid[r - 1][c - 1] != "#": return -1 dist = [[-1] * c for _ in range(r)] dist[0][0] = 0 queue = deque([(0, 0)]) while queue: y, x = queue.popleft() for ny, nx in neighbors(y, x): if dist[ny][nx] == -1: dist[ny][nx] = dist[y][x] + 1 queue.append((ny, nx)) return dist[r - 1][c - 1] print(count_islands())print(shortest_path())const lines = require("fs").readFileSync(0, "utf8").split("\n");const [r, c] = 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]];const isLand = (y, x) => y >= 0 && y < r && x >= 0 && x < c && grid[y][x] === "#"; // 깊이 우선 탐색(DFS)을 재귀로: 섬 하나를 모두 표시한다(깊이는 많아야 2,500)function fill(seen, y, x) { seen[y][x] = true; for (const [dy, dx] of STEPS) { const ny = y + dy, nx = x + dx; if (isLand(ny, nx) && !seen[ny][nx]) fill(seen, ny, nx); }} function countIslands() { const seen = Array.from({ length: r }, () => new Array(c).fill(false)); let islands = 0; for (let y = 0; y < r; y++) for (let x = 0; x < c; x++) if (grid[y][x] === "#" && !seen[y][x]) { islands++; fill(seen, y, x); } return islands;} // 너비 우선 탐색(BFS): 처음 닿을 때가 가장 짧은 거리다function shortestPath() { if (!isLand(0, 0) || !isLand(r - 1, c - 1)) return -1; const dist = Array.from({ length: r }, () => new Array(c).fill(-1)); dist[0][0] = 0; const queue = [[0, 0]]; for (let head = 0; head < queue.length; head++) { const [y, x] = queue[head]; for (const [dy, dx] of STEPS) { const ny = y + dy, nx = x + dx; if (isLand(ny, nx) && dist[ny][nx] === -1) { dist[ny][nx] = dist[y][x] + 1; queue.push([ny, nx]); } } } return dist[r - 1][c - 1];} console.log(countIslands());console.log(shortestPath());import { readFileSync } from "node:fs"; const lines: string[] = readFileSync(0, "utf8").split("\n");const [r, c]: 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]];const isLand = (y: number, x: number): boolean => y >= 0 && y < r && x >= 0 && x < c && grid[y][x] === "#"; // 깊이 우선 탐색(DFS)을 재귀로: 섬 하나를 모두 표시한다(깊이는 많아야 2,500)function fill(seen: boolean[][], y: number, x: number): void { seen[y][x] = true; for (const [dy, dx] of STEPS) { const ny = y + dy, nx = x + dx; if (isLand(ny, nx) && !seen[ny][nx]) fill(seen, ny, nx); }} function countIslands(): number { const seen: boolean[][] = Array.from({ length: r }, () => new Array(c).fill(false)); let islands = 0; for (let y = 0; y < r; y++) for (let x = 0; x < c; x++) if (grid[y][x] === "#" && !seen[y][x]) { islands++; fill(seen, y, x); } return islands;} // 너비 우선 탐색(BFS): 처음 닿을 때가 가장 짧은 거리다function shortestPath(): number { if (!isLand(0, 0) || !isLand(r - 1, c - 1)) return -1; const dist: number[][] = Array.from({ length: r }, () => new Array(c).fill(-1)); dist[0][0] = 0; const queue: [number, number][] = [[0, 0]]; for (let head = 0; head < queue.length; head++) { const [y, x] = queue[head]; for (const [dy, dx] of STEPS) { const ny = y + dy, nx = x + dx; if (isLand(ny, nx) && dist[ny][nx] === -1) { dist[ny][nx] = dist[y][x] + 1; queue.push([ny, nx]); } } } return dist[r - 1][c - 1];} console.log(countIslands());console.log(shortestPath());import java.io.BufferedReader;import java.io.IOException;import java.io.InputStreamReader;import java.util.ArrayDeque;import java.util.Arrays;import java.util.StringTokenizer; public class Main { static int r, c; static String[] grid; static final int[] DY = {1, -1, 0, 0}, DX = {0, 0, 1, -1}; static boolean isLand(int y, int x) { return y >= 0 && y < r && x >= 0 && x < c && grid[y].charAt(x) == '#'; } // 깊이 우선 탐색(DFS)을 재귀로: 섬 하나를 모두 표시한다(깊이는 많아야 2,500) static void fill(boolean[][] seen, int y, int x) { seen[y][x] = true; for (int d = 0; d < 4; d++) { int ny = y + DY[d], nx = x + DX[d]; if (isLand(ny, nx) && !seen[ny][nx]) fill(seen, ny, nx); } } static int countIslands() { boolean[][] seen = new boolean[r][c]; int islands = 0; for (int y = 0; y < r; y++) for (int x = 0; x < c; x++) if (grid[y].charAt(x) == '#' && !seen[y][x]) { islands++; fill(seen, y, x); } return islands; } // 너비 우선 탐색(BFS): 처음 닿을 때가 가장 짧은 거리다 static int shortestPath() { if (!isLand(0, 0) || !isLand(r - 1, c - 1)) return -1; int[][] dist = new int[r][c]; for (int[] row : dist) Arrays.fill(row, -1); ArrayDeque<int[]> queue = new ArrayDeque<>(); dist[0][0] = 0; queue.addLast(new int[] {0, 0}); while (!queue.isEmpty()) { int[] cur = queue.pollFirst(); for (int d = 0; d < 4; d++) { int ny = cur[0] + DY[d], nx = cur[1] + DX[d]; if (isLand(ny, nx) && dist[ny][nx] == -1) { dist[ny][nx] = dist[cur[0]][cur[1]] + 1; queue.addLast(new int[] {ny, nx}); } } } return dist[r - 1][c - 1]; } 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 String[r]; for (int y = 0; y < r; y++) grid[y] = in.readLine().trim(); System.out.println(countIslands()); System.out.println(shortestPath()); }}using System;using System.Collections.Generic; class Program{ static int r, c; static string[] grid; static readonly int[] DY = { 1, -1, 0, 0 }, DX = { 0, 0, 1, -1 }; static bool IsLand(int y, int x) => y >= 0 && y < r && x >= 0 && x < c && grid[y][x] == '#'; // 깊이 우선 탐색(DFS)을 재귀로: 섬 하나를 모두 표시한다(깊이는 많아야 2,500) static void Fill(bool[,] seen, int y, int x) { seen[y, x] = true; for (int d = 0; d < 4; d++) { int ny = y + DY[d], nx = x + DX[d]; if (IsLand(ny, nx) && !seen[ny, nx]) Fill(seen, ny, nx); } } static int CountIslands() { var seen = new bool[r, c]; int islands = 0; for (int y = 0; y < r; y++) for (int x = 0; x < c; x++) if (grid[y][x] == '#' && !seen[y, x]) { islands++; Fill(seen, y, x); } return islands; } // 너비 우선 탐색(BFS): 처음 닿을 때가 가장 짧은 거리다 static int ShortestPath() { if (!IsLand(0, 0) || !IsLand(r - 1, c - 1)) return -1; var dist = new int[r, c]; for (int y = 0; y < r; y++) for (int x = 0; x < c; x++) dist[y, x] = -1; var queue = new Queue<(int, int)>(); dist[0, 0] = 0; queue.Enqueue((0, 0)); while (queue.Count > 0) { var (y, x) = queue.Dequeue(); for (int d = 0; d < 4; d++) { int ny = y + DY[d], nx = x + DX[d]; if (IsLand(ny, nx) && dist[ny, nx] == -1) { dist[ny, nx] = dist[y, x] + 1; queue.Enqueue((ny, nx)); } } } return dist[r - 1, c - 1]; } static void Main() { string[] first = Console.ReadLine().Split(' ', StringSplitOptions.RemoveEmptyEntries); r = int.Parse(first[0]); c = int.Parse(first[1]); grid = new string[r]; for (int y = 0; y < r; y++) grid[y] = Console.ReadLine().Trim(); Console.WriteLine(CountIslands()); Console.WriteLine(ShortestPath()); }}#include <iostream>#include <queue>#include <string>#include <utility>#include <vector> int r, c;std::vector<std::string> grid;const int DY[4] = {1, -1, 0, 0}, DX[4] = {0, 0, 1, -1}; bool isLand(int y, int x) { return y >= 0 && y < r && x >= 0 && x < c && grid[y][x] == '#'; } // 깊이 우선 탐색(DFS)을 재귀로: 섬 하나를 모두 표시한다(깊이는 많아야 2,500)void fill(std::vector<std::vector<bool>>& seen, int y, int x) { seen[y][x] = true; for (int d = 0; d < 4; d++) { int ny = y + DY[d], nx = x + DX[d]; if (isLand(ny, nx) && !seen[ny][nx]) fill(seen, ny, nx); }} int countIslands() { std::vector<std::vector<bool>> seen(r, std::vector<bool>(c, false)); int islands = 0; for (int y = 0; y < r; y++) for (int x = 0; x < c; x++) if (grid[y][x] == '#' && !seen[y][x]) { islands++; fill(seen, y, x); } return islands;} // 너비 우선 탐색(BFS): 처음 닿을 때가 가장 짧은 거리다int shortestPath() { if (!isLand(0, 0) || !isLand(r - 1, c - 1)) return -1; std::vector<std::vector<int>> dist(r, std::vector<int>(c, -1)); std::queue<std::pair<int, int>> q; dist[0][0] = 0; q.push({0, 0}); while (!q.empty()) { auto [y, x] = q.front(); q.pop(); for (int d = 0; d < 4; d++) { int ny = y + DY[d], nx = x + DX[d]; if (isLand(ny, nx) && dist[ny][nx] == -1) { dist[ny][nx] = dist[y][x] + 1; q.push({ny, nx}); } } } return dist[r - 1][c - 1];} int main() { std::cin >> r >> c; grid.resize(r); for (auto& row : grid) std::cin >> row; std::cout << countIslands() << "\n" << shortestPath() << "\n";}#include <stdbool.h>#include <stdio.h> static int r, c;static char grid[50][52];static bool seen[50][50];static int dist[50][50];static const int DY[4] = {1, -1, 0, 0}, DX[4] = {0, 0, 1, -1}; static bool is_land(int y, int x) { return y >= 0 && y < r && x >= 0 && x < c && grid[y][x] == '#';} /* 깊이 우선 탐색(DFS)을 재귀로: 섬 하나를 모두 표시한다(깊이는 많아야 2,500) */static void fill(int y, int x) { seen[y][x] = true; for (int d = 0; d < 4; d++) { int ny = y + DY[d], nx = x + DX[d]; if (is_land(ny, nx) && !seen[ny][nx]) fill(ny, nx); }} static int count_islands(void) { int islands = 0; for (int y = 0; y < r; y++) for (int x = 0; x < c; x++) if (grid[y][x] == '#' && !seen[y][x]) { islands++; fill(y, x); } return islands;} /* 너비 우선 탐색(BFS): 칸마다 한 번만 넣으니 큐는 r*c칸이면 된다 */static int shortest_path(void) { static int qy[2500], qx[2500]; if (!is_land(0, 0) || !is_land(r - 1, c - 1)) return -1; for (int y = 0; y < r; y++) for (int x = 0; x < c; x++) dist[y][x] = -1; int head = 0, tail = 0; dist[0][0] = 0; qy[tail] = 0, qx[tail] = 0, tail++; while (head < tail) { int y = qy[head], x = qx[head]; head++; for (int d = 0; d < 4; d++) { int ny = y + DY[d], nx = x + DX[d]; if (is_land(ny, nx) && dist[ny][nx] == -1) { dist[ny][nx] = dist[y][x] + 1; qy[tail] = ny, qx[tail] = nx, tail++; } } } return dist[r - 1][c - 1];} int main(void) { scanf("%d %d", &r, &c); for (int y = 0; y < r; y++) scanf("%51s", grid[y]); printf("%d\n", count_islands()); printf("%d\n", shortest_path()); return 0;}// 칸 (y, x)는 목록에서 y * c + x 자리에 둔다(2,500칸이라 목록 하나에 들어간다)땅인가(y, x){ 돌려주기 y >= 0 && y < r && x >= 0 && x < c && grid[y][x] == "#";} // 깊이 우선 탐색(DFS)을 스택으로 — 크레이콘 재귀는 몇천 단계에서 멈춰서 2,500칸 섬은 위험하다섬세기(){ seen = 새목록(r * c, 거짓); islands = 0; 반복 (y = 0; y < r; y++) { 반복 (x = 0; x < c; x++) { 만약 (grid[y][x] == "#" && !seen[y * c + x]) { islands += 1; seen[y * c + x] = 참; stack = [y * c + x]; 동안 (stack.개수 > 0) { cell = stack[stack.개수 - 1]; stack.자리빼기(stack.개수 - 1); cy = 수학.몫(cell, c); cx = cell % c; 반복 (d = 0; d < 4; d++) { ny = cy + DY[d]; nx = cx + DX[d]; 만약 (땅인가(ny, nx) && !seen[ny * c + nx]) { seen[ny * c + nx] = 참; stack.넣기(ny * c + nx); } } } } } } 돌려주기 islands;} // 너비 우선 탐색(BFS): 처음 닿을 때가 가장 짧은 거리다. 칸마다 한 번만 넣으니 큐는 앞 자리(head)만 옮긴다가장짧은길(){ 만약 (!땅인가(0, 0) || !땅인가(r - 1, c - 1)) { 돌려주기 -1; } dist = 새목록(r * c, -1); dist[0] = 0; queue = [0]; head = 0; 동안 (head < queue.개수) { cell = queue[head]; head += 1; cy = 수학.몫(cell, c); cx = cell % c; 반복 (d = 0; d < 4; d++) { ny = cy + DY[d]; nx = cx + DX[d]; 만약 (땅인가(ny, nx) && dist[ny * c + nx] == -1) { dist[ny * c + nx] = dist[cell] + 1; queue.넣기(ny * c + nx); } } } 돌려주기 dist[r * c - 1];} 크기 = 콘솔.수들읽기();r = 크기[0];c = 크기[1];grid = [];반복 (i = 0; i < r; i++){ grid.넣기(콘솔.줄읽기().공백제거());}DY = [1, -1, 0, 0];DX = [0, 0, 1, -1];콘솔.쓰기(섬세기());콘솔.쓰기(가장짧은길());