[탐색/BFS] 백준 2178 미로 탐색 - Python

 

[ Contents ]

 

 

1. 문제 (링크 참조)

2178번: 미로 탐색

 

 

 

2. 문제 풀이

 미로를 최단 거리로 탈출해야하는 문제입니다.

 

2022.02.23 - [Algorithm] - [Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자

[Algorithm] 너비 우선 탐색(BFS), 가까운 주변부터 찾자

 BFS문제입니다. 길을 지날 때마다 거리를 1씩 늘리며 표시합니다.

 

 

3. 코드

import sys
from collections import deque
input = sys.stdin.readline

N, M = map(int, input().split())
maze = []
for _ in range(N):
    maze.append([int(i) for i in input().rstrip()])

direction = [(1,0), (-1, 0), (0, 1), (0, -1)] #상하좌우
queue = deque([(0, 0)]) #0,0부터 시작

 입력이 '붙어서' 주어집니다. 문자열로 받아서 하나씩 떼어줍니다.

 

 

#bfs 탐색
while queue:
    x, y = queue.popleft()
    for dx, dy in direction:
        nx = x + dx
        ny = y + dy

        #미로 공간 벗어나면 건너뛰기
        if nx < 0 or ny < 0 or nx >= N or ny >= M:
            continue

        #벽인 경우 무시
        if maze[nx][ny] == 0:
            continue

        #처음 방문하면 거리기록
        if maze[nx][ny] == 1:
            maze[nx][ny] += maze[x][y]
            queue.append((nx, ny))

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

 BFS탐색으로 풀이합니다. 미로 공간을 벗어나거나 벽이면 건너뛰고, 처음 방문하면 거리를 기록하고 탐색합니다.