February 12, 2023

2178번: 미로 탐색

문제 요약

• N * M 크기의 미로가 주어졌을 때, 1은 이동할 수 있는 칸이고 0은 이동할 수 없는 칸을 의미하는 경우 (1, 1)에서 출발하여 (N, M) 까지의 최단거리 출력
• 시간 제한 : 1초

문제 풀이

from collections import deque

N, M = map(int, input().split())
board = [list(map(int, list(input()))) for _ in range(N)]
visited = [[False] * M for _ in range(N)]
dr = [0, 1, 0, -1]
dc = [1, 0, -1, 0]

def bfs():
    q = deque()

    # (row, col, cost)
    q.append((0, 0, 1))
    visited[0][0] = True

    while (q):
        row, col, cost = q.popleft()

        for i in range(len(dr)):
            nr = row + dr[i]
            nc = col + dc[i]

            if (nr < N and nr >= 0 and nc < M and nc >= 0 and board[nr][nc] == 1 and visited[nr][nc] == False):
                visited[nr][nc] = True
                q.append((nr, nc, cost + 1))

                if ((nr, nc) == (N - 1, M - 1)):
                    print(cost + 1)
                    return

bfs()

• BFS 이용