[파이썬] 백준 2178번 문제: 미로 탐색

미로 탐색

📄 문제

문제

N×M크기의 배열로 표현되는 미로가 있다.

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

출력

첫째 줄에 지나야 하는 최소의 칸 수를 출력한다. 항상 도착위치로 이동할 수 있는 경우만 입력으로 주어진다.

🧞 풀이

풀이

# 백준 2178번 문제: 미로 탐색

from collections import deque                                                               # 큐를 위한 deque 불러오기

n, m = map(int, input().split())                                                            # n, m 입력 및 할당

dx = [1, -1, 0, 0]                                                                          # 좌우로 움직일 수 있게 dx 할당
dy = [0, 0, 1, -1]                                                                          # 상하로 움직일 수 있게 dy 할당

maze = []                                                                                   # 미로를 위한 빈 배열 할당

for _ in range(n):                                                                          # n만큼 반복
    maze.append(list(map(int, input())))                                                    # 미로 입력 값 받아서 2차원 배열 만들기

Q = deque()                                                                                 # 빈 큐 할당
check = [[0] * m for _ in range(n)]                                                         # 방문 시 체크할 빈 n * m 크기의 2차원 배열 할당

check[0][0] = -1                                                                            # 시작 지점은 체크 (-1)로 표시
Q.append((0, 0, 1))                                                                         # 큐에 0, 0, 1 추가

while Q:                                                                                    # 큐에 요소가 있는 경우에 계속 반복
    x, y, dis = Q.popleft()                                                                 # 큐의 첫 요소를 pop하여 x, y, dis에 할당

    if x == m - 1 and y == n - 1:                                                           # x 혹은 y가 m, n으로 끝 자리에 도달했을 때,
        print(dis)                                                                          # 거리를 나타내는 dis 값 출력 (BFS는 최단거리를 출력해줌)
        break                                                                               # 반복문 종료

    for i in range(4):                                                                      # 상하좌우로 움직여야 하기에 4만큼 반복
        nx = dx[i] + x                                                                      # x값 변경하며 좌우로 움직일 수 있게 함
        ny = dy[i] + y                                                                      # y값 변경하며 상하로 움직일 수 있게 함

        if 0 <= nx < m and 0 <= ny < n and check[ny][nx] != -1 and maze[ny][nx] != 0:       # nx, ny가 미로 안에 있으면서, 방문하지 않았고, 해당 위치가 미로의 벽(0)이 아닐 경우,
                check[ny][nx] = -1                                                          # 해당 위치를 방문함(-1)로 바꿔줌
                Q.append((nx, ny, dis + 1))                                                 # Q에 움직인 x, y 위치와 1 추가한 거리를 다시 추가해 줌