백준 2178번 미로 탐색 | python | bfs

문제

링크

풀이

이코테의 미로 탈출 문제와 완전히 동일하다.

이 문제 또한 bfs()를 이용해주면 되는데, 가장 왼쪽 상단 지점부터 시작하여 bfs()를 수행해 이동 가능한 칸을 차례차례 방문한다.

이 때 방문 여부와 이동 거리를 표시하기 위해, 특정 노드를 방문하면 그 이전 노드의 거리에 1을 더한 값을 arr의 현재 좌표 값으로 갱신해주면 된다.

# 상하좌우 1이있으면 갈 곳이 있다는 뜻이고,
# 계속 누적해서 움직이면 됨
import sys
from collections import deque

input = sys.stdin.readline
n, m = map(int, input().split())

arr = []
for _ in range(n):
    arr.append(list(map(int, input().strip())))


d = [(0, -1), (0, 1), (1, 0), (-1, 0)]


def bfs(y, x):
    q = deque()
    q.append((y, x))
    while q:
        y, x = q.popleft()
        for dy, dx in d:
            Y, X = y + dy, x + dx
            if (0 <= Y < n) and (0 <= X < m) and arr[Y][X] == 1:
                q.append((Y, X))
                arr[Y][X] = arr[y][x] + 1  # 방문 및 현재까지 지나간 칸 수(이동 거리)를 의미


bfs(0, 0)
print(arr[n - 1][m - 1])