# 백준 2178번 미로 탐색

## Solution

import sys
from collections import deque

n, m = map(int, input().split())
graph = [list(map(int, input().strip())) for _ in range(n)]
visit = [[False] * m for _ in range(n)]
dist = [[0] * m for _ in range(n)]
move = [(-1, 0), (0, 1), (1, 0), (0, -1)]

def bfs(x0, y0):
queue = deque([[x0, y0]])
visit[x0][y0] = True

while queue:
x, y = queue.popleft()
for dx, dy in move:
nx = x + dx
ny = y + dy

if 0 <= nx < n and 0 <= ny < m and not visit[nx][ny] and graph[nx][ny] == 1:
queue.append([nx, ny])
visit[nx][ny] = True
dist[nx][ny] = dist[x][y] + 1

bfs(0, 0)
print(dist[n - 1][m - 1] + 1)
• 모범 풀이
import sys
from collections import deque

n, m = list(map(int, si().split()))
a = [si().strip() for _ in range(n)]

dist = [[0] * m for _ in range(n)]
dir = [[1, 0], [0, 1], [-1, 0], [0, -1]]

def bfs():
queue = deque()
queue.append(0)
queue.append(0)
dist[0][0] = 1

while queue:
x = queue.popleft()
y = queue.popleft()
for dx, dy in dir:
nx, ny = x + dx, y + dy
if nx < 0 or nx >= n or ny < 0 or ny >= m: continue
if dist[nx][ny] != 0: continue
if a[nx][ny] == '0': continue
dist[nx][ny] = dist[x][y] + 1
queue.append(nx)
queue.append(ny)

bfs()
print(dist[n - 1][m - 1])
• java 풀이
import java.io.*;
import java.lang.reflect.Array;
import java.util.*;

public class Main {
static StringBuilder sb = new StringBuilder();

static int N, M;
static String[] a;
static int[][] dist;
static boolean[][] visit;
static int[][] dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
static ArrayList<Integer> group;

static void input() {
N = scan.nextInt();
M = scan.nextInt();
a = new String[N];
for (int i = 0; i < N; i++)
a[i] = scan.nextLine();
visit = new boolean[N][M];
dist = new int[N][M];
}

// x, y 를 갈 수 있다는 걸 알고 방문한 상태
static void bfs(int x, int y) {
// dist 배열 초기화
for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) dist[i][j] = -1;

// (x, y)를 Q에 넣어주고, visit 표시와 dist 값 초기화
dist[x][y] = 1;
visit[x][y] = true;

// BFS 과정 시작
while (!Q.isEmpty()) {
x = Q.poll();
y = Q.poll();
for (int k = 0; k < 4; k++) {
int nx = x + dir[k][0];
int ny = y + dir[k][1];
if (nx < 0 || ny < 0 || nx >= N || ny >= M) continue;  // 지도를 벗어나는 곳으로 가는가?
if (a[nx].charAt(ny) == '0') continue;  // 갈 수 있는 칸인지 확인해야 한다.
if (visit[nx][ny]) continue;  // 이미 방문한 적이 있는 곳인가?
visit[nx][ny] = true;
dist[nx][ny] = dist[x][y] + 1;
}
}
}

static void pro() {
// 시작점이 (0, 0)인 탐색 시작
bfs(0, 0);

// (N-1, M-1)까지 필요한 최소 이동 횟수 출력
System.out.println(dist[N - 1][M - 1]);
}

public static void main(String[] args) {
input();
pro();
}

StringTokenizer st;

}

public FastReader(String s) throws FileNotFoundException {
}

String next() {
while (st == null || !st.hasMoreElements()) {
try {
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}

int nextInt() {
return Integer.parseInt(next());
}

long nextLong() {
return Long.parseLong(next());
}

double nextDouble() {
return Double.parseDouble(next());
}

String nextLine() {
String str = "";
try {
}