[백준 파이썬] 2178 미로 탐색

📌문제 출처

백준 단계별 문제풀이 - 그래프와 순회
https://www.acmicpc.net/problem/2178

2178번: 미로 탐색

❓ 문제

❗ 풀이

• bfs 활용

📗 풀이 코드

from collections import deque
input = sys.stdin.readline
n,m = map(int,input().split())
maze = [list(map(int,input().strip())) for _ in range(n)]
# 해당 칸으로 진행 가능한지, 진행하면 최소로 진행한 거리인지 확인하는 함수
def bfs(row,col,cnt):
    stack = deque()
    stack.append([row,col,cnt])
    while stack :
        row,col,cnt = stack.popleft()
        if (row==n-1)&(col==m-1): # 최초로 마지막 칸에 도착했다면
            return(cnt)
        for d_row,d_col in [[-1,0],[1,0],[0,-1],[0,1]] : # 상하좌우 이동으로 도착할 다음 칸
            n_row, n_col = row+d_row, col+d_col # 이동하려는 칸 초기화
            if (0<=n_row<n) & (0<=n_col<m) : # 새로 이동하는 칸이 maze 내 범위이고
                if maze[n_row][n_col] == 1 : # 이번 칸이 처음 이동하는 칸이라면
                    stack.append([n_row,n_col,cnt+1]) # 이동하는 칸에서 또 확인
                    maze[n_row][n_col] = cnt+1 # 다음번 도착하는 칸 초기화
print(bfs(0,0,1)) # 이번 행, 이번 열, 이번 칸 도착 시 밟은 칸 수

📗 코드 해설

• bfs라는 함수를 단 한 번만 돌려서 while문 내에서 deque의 성질을 활용하여 시간을 단축한다.
• 특정 칸에 도착 후 해당 칸에서 상하좌우 칸 중 이동 가능한 곳으로 이동하는 경우만 stack에 넣어준다.
• 이동 가능한 칸에서도 처음 이동하는 칸으로만 움직이기에 시간을 단축시킬 수 있다.