[백준 2178번] 미로 탐색

2178번: 미로 탐색

from collections import deque

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

maze = [list(map(int,list(input()))) for _ in range(n)]
visited = [[-1]*m for _ in range(n)]

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

def bfs():
    visited[0][0] = 1

    queue = deque([(0,0)])

    while queue:
        cur_x,cur_y = queue.popleft()

        if cur_x == n-1 and cur_y == m-1:
            return visited[cur_x][cur_y]

        for i in range(4):
            nx = cur_x + dx[i]
            ny = cur_y + dy[i]

            if 0 <= nx < n and 0 <= ny < m and visited[nx][ny] == -1 and maze[nx][ny] == 1:
                visited[nx][ny] = visited[cur_x][cur_y] + 1
                queue.append((nx,ny))
    return -1

print(bfs())

이번 문제는 (0,0)에서 (n-1,m-1)까지 이동하는 최소 거리를 구하는 문제이다.

 

BFS 알고리즘을 사용하여 최소 거리를 구하면 되는데, 칸을 셀 때 시작 위치와 도착 위치도 포함한다는 것을 조심하면 된다.

 

기본적인 BFS 예제를 통해 복습해볼 수 있던 문제였다 :)