백준 2178 문제 풀이 python

🐒 미로 탐색

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

✍ 나의 풀이

from collections import deque




n, m = map(int, input().split())


dx = [0,0,-1,1]
dy = [-1,1,0,0]

def bfs(x,y):
    queue = deque()
    queue.append((x,y))
    
    while queue:
        x, y = queue.popleft()
        
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            if nx<0 or nx>=n or ny<0 or ny>=m: 
                continue
            elif matrix[nx][ny] == 1:
                matrix[nx][ny] = matrix[x][y] + 1
                queue.append((nx,ny))
    
    return matrix[n-1][m-1]


matrix = []
for i in range(n):
    matrix.append(list(map(int , input())))

print(bfs(0,0))

n x m 미로에서
[1,1]칸에서 부터 [n,m]칸까지 최소한의 이동횟수를 구하는 문제이다.

BFS구현은 어느정도 할 수 있겠지만 최소한의 이동횟수를 구하는 아이디어가 안떠올라서 어려웠던 문제이다.

🧠 문제 이해

현재칸 까지의 이동횟수를 캐싱하기

다음칸으로 이동할때마다 다음칸에 현재 칸까지의 이동횟수 + 1 을 저장한다.