[BOJ] 2178. 미로 탐색

📌 문제 제목

문제 링크: BOJ 2178

---

🗒️ 문제 설명

NxM 크기의 배열로 표현되는 미로가 있다.

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다.

(1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램.

시간 제한: 1초

메모리 제한: 192MB

2 <= N, M <= 100

---

💡 문제 해결 아이디어

• NM이 10,000 이기 때문에 O(NM)의 시간복잡도를 가지는 알고리즘 사용.
• BFS를 사용해서 각 칸과 시작점 사이의 거리를 구할 수 있다.

---

⌛️ 시간 복잡도

• O(NM)

---

✅ 최종 코드

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

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

dist = [[-1] * M for _ in range(N)]
direction = [(-1, 0), (1, 0), (0, -1), (0, 1)]

queue = deque([(0, 0)])
while queue:
    xp, yp = queue.popleft()
    dist[0][0] = 1
    for dx, dy in direction:
        nx, ny = xp + dx, yp + dy
        if not (0 <= nx < N and 0 <= ny < M):
            continue
        if dist[nx][ny] == -1 and graph[nx][ny] == 1:
            queue.append((nx, ny))
            dist[nx][ny] = dist[xp][yp] + 1
print(dist[N-1][M-1])