BOJ 2178. 미로 탐색 (Python)

문제

BOJ 2178

내가 생각한 풀이

시작 지점이 무조건 (1, 1)이므로 queue에 (0, 0)을 넣고 BFS 수행

visited 배열이 아닌 dist 배열 (거리값을 가지는 2차원 배열)을 사용

BFS를 돌 때 popleft한 값이 도착지점의 좌표와 같으면 BFS 종료

BFS가 종료되면 dist 배열의 도착좌표 값을 출력

 

코드 (Python)

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

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

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


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


bfs()

print(dist[N-1][M-1])