---

문제 출처 : https://www.acmicpc.net/problem/2178
난이도 : 실버 1

---

문제 파악

N x M 미로가 주어진다.
1 은 이동 가능, 0 은 이동 불가능.

(0,0)에서 출발해서 (N-1, M-1)까지 도착할 때
지나야 하는 칸 수의 최소값(최단거리) 을 출력해야 한다.

즉,

• 경로가 존재한다.
• 우리는 “가장 적은 칸을 밟는 경로”의 길이를 원한다.

이런 조건이면 대표적으로 BFS(너비 우선 탐색) 로 풀 수 있다.

왜 BFS인가?

BFS는 “가까운 것부터” 탐색한다.

시작점에서 한 번에 갈 수 있는 칸(거리 2),
그 다음에 갈 수 있는 칸(거리 3)…

이 순서로 퍼져 나가니까
처음 도착하는 순간이 최단거리가 된다.

DFS는 깊게 파고들었다가 돌아오므로
최단거리가 보장되지 않는다.

---

내가 틀렸던 포인트

처음에 cnt += 1 이런 식으로
큐에서 pop될 때마다 숫자를 올려서 기록했다가 틀렸다.

그건 “최단거리”가 아니라 “방문 순서 번호”가 된다.

최단거리는 이렇게 해야 한다.

다음 칸의 거리 = 현재 칸의 거리 + 1

graph[ny][nx] = graph[y][x] + 1

이게 이 문제의 핵심이었다.

---

해답 및 풀이

from collections import deque
import sys
input = sys.stdin.readline

dx = [-1,1,0,0]
dy = [0,0,-1,1]

def bfs(X,Y):
    queue = deque()
    queue.append((X,Y))

    while queue:
        x, y = queue.popleft()

        # 상하좌우 탐색
        for d in range(4):
            nx = x + dx[d]
            ny = y + dy[d]

            if 0 <= nx < M and 0 <= ny < N and graph[ny][nx] == 1:
                graph[ny][nx] = graph[y][x] + 1
                queue.append((nx,ny))

N, M = map(int,input().split())
graph = [list(map(int, input().rstrip())) for _ in range(N)]


bfs(0,0) # (0,0) 부터 돌면서 
print(graph[N-1][M-1])

방향벡터를 활용한 4방향 BFS 탐색 코드는 어제와 그제 풀어본
유기농 배추 문제와
단지번호붙이기 문제가 도움이 됐다.