[python] 백준 2178번: 미로 탐색(BFS)

# 2178 미로 탐색

https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

⭐ 코드

import sys
input = sys.stdin.readline
from collections import deque
N, M = map(int, input().split())

graph = [list(map(int, input().strip())) for _ in range(N)]
visited = [[-1] * M for _ in range(N)]
dx, dy = [0,0,-1,1], [-1,1,0,0]
queue = deque()
queue.append((0,0))
visited[0][0] = 1

while queue:
    x, y = queue.popleft()

    for i in range(4):
        nx, ny = dx[i] + x, dy[i] + y

        if nx < 0 or nx >= N or ny < 0 or ny >= M:
            continue
        if graph[nx][ny] == 1 and visited[nx][ny] == -1:
            visited[nx][ny] = visited[x][y] + 1
            queue.append((nx,ny))

print(visited[N-1][M-1])

📝 풀이

시작지점이 1,1이고 최종적으로 미로의 크기만큼인 N, M까지의 최단경로를 구해야 한다.

미로에서 1은 지나갈 수 있는 길이며, 0은 지나갈 수 없는 길이므로 방문처리할 때 구분을 잘 해줘야 한다.

🔓 정답 코드 뜯어보기

from collections import deque
N, M = map(int, input().split())

graph = [list(map(int, input().strip())) for _ in range(N)]
visited = [[-1] * M for _ in range(N)]
dx, dy = [0,0,-1,1], [-1,1,0,0]
queue = deque()
queue.append((0,0))
visited[0][0] = 1

input값들이 붙어서 주어지므로, split()을 제외하고 입력 받아준다. 세로만큼의 반복문을 실행해 graph를 생성해주고 방문처리를 위한 N*M 2차원 리스트 visited를 생성해준다.

 

맨처음 시작하는 위치가 (1,1)이지만, 출력할 때 1씩 차감시켜줄 것이므로 편의상 0,0으로 시작하도록 설정해준다. 방문한 처음 인덱스는 1로 시작한다고 했으므로 visited[0][0] = 1로 방문처리해준다.

while queue:
    x, y = queue.popleft()

    for i in range(4):
        nx, ny = dx[i] + x, dy[i] + y

        if nx < 0 or nx >= N or ny < 0 or ny >= M:
            continue
        if graph[nx][ny] == 1 and visited[nx][ny] == -1:
            visited[nx][ny] = visited[x][y] + 1
            queue.append((nx,ny))

print(visited[N-1][M-1])

# graph
# [
# [1, -1, 9, 10, 11, 12], 
# [2, -1, 8, -1, 12, -1], 
# [3, -1, 7, -1, 13, 14], 
# [4, 5, 6, -1, 14, 15]
# ]

위에서 생성해준 queue가 빌 때까지 while문을 실행시켜주고, popleft를 통해서 x,y값을 할당시켜준다. 방향탐색을 하면서 범위에 벗어나지 않고, graph[nx][ny] == 1 (갈 수 있는 땅) 이면서 visited[nx][ny] == -1 (방문하지 않은 곳)이면 이전의 visited[x][y]값에 1을 추가해서 visited[nx][ny]에 저장시켜준다.

 

그러고 난 후 탐색했던 곳을 다시 queue에 삽입시켜주고 최종적으로 더 이상 탐색할 곳이 없다면 위와 같이 graph가 생성된다. visited[N-1][M-1]을 통해 목적지 값을 출력시켜준다.