[백준] 2178번 - 미로 탐색 (파이썬)

https://www.acmicpc.net/problem/2178

# 미로 탐색
import sys
from collections import deque
input = sys.stdin.readline


def go(x, y):
    q = deque()
    q.append((x, y))
    while q:
        x, y = q.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if nx <= -1 or nx >= N or ny <= -1 or ny >= M:
                continue
            if arr[nx][ny] == 0:
                continue
            elif arr[nx][ny] == 1:
                q.append((nx, ny))
                arr[nx][ny] = arr[x][y] + 1


N, M = map(int, input().split())
arr = []
for i in range(N):
    arr.append(list(map(int, input().strip())))
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

go(0, 0)
print(arr[N-1][M-1])

 

BFS

1. 시작지점을 q에 append하고 시작

2. q가 빌 때까지 현재위치의 좌,우,위,아래 4방향 확인

  - 해당 위치의 값이 0이면(이동불가), continue

  - 해당 위치의 값이 1이면(이동가능), q에 그 위치(x,y)를 append하고 1증가

3. arr[N-1][M-1] 출력 (도착위치로 이동할 수 있을 경우만 입력으로 주어짐)

 

(1,1)에서 시작하는 것을 (0,0)으로 생각하고 마지막에 출력할 때 -1씩 해주었다.