[백준 2178번] 미로 탐색 (Python/파이썬)

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

2178번: 미로 탐색

특정 위치까지 몇칸을 가야하는지 구하는 문제로 BFS를 사용하여 해결하였다.

탐색을 하면서 갈래길을 탐색해야하므로 상/하/좌/우를 검사하기 위한 좌표 리스트를 Cross_x, Cross_y로 만들었다.

그리고 BFS를 작성하고 나니 어떻게 특정 위치까지의 거리를 계산할까 하다가 BFS로 탐색한 깊이 지도를 하나 만들었다.

이 지도는 처음 시작부분부터 최소 몇번을 가야지 도달할 수 있는지 저장해놓는 지도로 BFS를 하면서 저장한다.

지도의 좌표를 출력하면서 코드는 끝난다.

 

지도를 만들어야겠다는 생각만 있으면 간단한 BFS로 해결할 수 있다.

코드는 다음과 같다.

import sys
from collections import deque
input = sys.stdin.readline
N,M = map(int,input().split())
visited = [[False]*M for _ in range(N)]
queue = deque([])
depth_map = [[0]*M for _ in range(N)]
depth_map[0][0] = 1
maze = []
for _ in range(N):
    maze.append(list(map(int,input().rstrip())))

Cross_x = [1,-1,0,0]
Cross_y = [0,0,1,-1]

def BFS(a,b):
    global depth
    queue.append((a,b))
    visited[a][b] = True
    while queue:
        (a, b) = queue.popleft()
        for i in range(4):
            x = a + Cross_x[i]
            y = b + Cross_y[i]
            if x >= 0 and y >= 0 and x <= N-1 and y <= M-1 and maze[x][y] == 1:
                if not visited[x][y]:
                    queue.append((x,y))
                    visited[x][y] = True
                    depth_map[x][y] = depth_map[a][b] + 1
                    if x == N-1 and y == M-1:
                      return 
BFS(0,0)
print(depth_map[N-1][M-1])

 

 

글이나 코드에 대한 조언 모두 환영합니다.