알고리즘 스터디 - 백준 2178번 : 미로 탐색

문제 해석

미로 내에서 (0, 0)에서 (N, M)에 도착할 때 지나야하는 최소의 칸 수를 출력

BFS 알고리즘을 좌표로 변환하여 지나갈 수 있는 좌표를 찾으며 해당 위치에 도달하기까지의 거리를 계산하면 된다.

알고리즘 코드

• 이 방식은 기존 BFS를 이용해서 각 좌표에다가 지나온 거리를 저장하며 갱신하는 것이다.

N, M = map(int, input().split())

miro = []

for _ in range(N):
    M_list = list(input())
    miro.append(M_list)

distance = [[0] * M for _ in range(N)]

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

queue = [(0, 0)]
distance[0][0] = 1

while queue:
    x, y = queue.pop(0)

    if x == M-1 and y == N-1:
        print(distance[y][x])
        break

    for i in range(4):
        new_x = x + dx[i]
        new_y = y + dy[i]

        if 0 <= new_x < M and 0 <= new_y < N:
            if miro[new_y][new_x] == '1' and distance[new_y][new_x] == 0:
                queue.append((new_x, new_y))
                distance[new_y][new_x] = distance[y][x] + 1