[Python] Baekjoon - 2178. 미로 탐색

백준 2178번 미로 탐색 문제는 세로 N, 가로 M 길이의 미로의 왼쪽 맨 위칸에서 오른쪽 맨 아래칸까지 이동할 때 거쳐가는 칸의 최소 개수를 구하는 문제다. 최단 거리를 찾는 문제이므로 그래프 탐색 알고리즘 중 너비 우선 탐색(BFS)을 이용한다. 난이도는 실버 1이다.

 

백준 2178번 미로 탐색 문제 정보

알고리즘 분류

- 그래프 탐색

난이도

- 실버 1

 

미로 탐색 문제 요약

• 이동 불가능한 칸 0과 이동 가능한 칸 1로 구성된 NxM 크기의 미로가 있다.
• (1,1)에서 출발하여 (N, M)에 도착하기까지 거쳐가는 칸의 최소 개수를 구하는 문제다.
• 인접한 칸으로만 이동 가능하다.

 

문제 풀이 과정

• 최단거리 문제이기 때문에 그래프 탐색 알고리즘 BFS를 사용한다.
• 한번 방문한 곳은 다시 방문하지 않도록 visited 배열을 사용해야 한다.

 

코드

from collections import deque


# BFS를 이용하여 (0,0)부터 (N-1, M-1)까지 가는 최소 이동 횟수를 구하는 함수
def getMinDist():
    global N, M, board, visited

    queue = deque()
    queue.append((0, 0, 1)) # 시작점 추가
    visited[0][0] = 1
    dr, dc = [1,-1,0,0], [0,0,1,-1]

    while len(queue) > 0:
        hereR, hereC, hereDist = queue.popleft()

        # 도착하면 종료
        if (hereR, hereC) == (N-1, M-1):
            return hereDist

        # 상하좌우 이동 가능한지 확인
        for d in range(4):
            thereR, thereC = hereR + dr[d], hereC + dc[d]
            thereDist = hereDist + 1

            # 보드판 내에 있는지, 이동 가능한 칸인지, 이전에 방문하지는 않았는지 확인 후 큐에 추가
            if 0 <= thereR < N and 0 <= thereC < M and board[thereR][thereC] == '1' and visited[thereR][thereC] == 0:
                visited[thereR][thereC] = 1
                queue.append((thereR, thereC, thereDist))


if __name__ == '__main__':
    N, M = map(int, input().split())
    board = []
    visited = [[0 for _ in range(M)] for _ in range(N)]

    for _ in range(N):
        board.append([*input()])

    print(getMinDist())