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

문제

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

풀이

• N$\times$M 미로
  • 1: 이동할 수 있는 칸
  • 0: 이동할 수 없는 칸
• (1,1) 출발
• (N,M) 도착 최소 칸

최단거리를 찾는 문제이기 때문에 BFS를 사용하면 됩니다.

(0,0)에서 시작하여 상하좌우를 탐색하면서 미로를 탐색

def bfs():
    queue = deque([(0,0)]) # 시작 지점 삽입

    while queue:
        x,y = queue.popleft()

		# 상하좌우 탐색
        for i in range(4):
            nx,ny = x+dx[i], y+dy[i]
            if  0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 1: # 범위 내 && 이동할 수 있는 경로
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx,ny))

모든 경로 탐색 후 (N,M)까지 최소 이동횟수를 찾기 때문에 graph[n-1][m-1]을 출력해주면 문제 해결 😁

코드

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

def bfs():
    queue = deque([(0,0)])

    while queue:
        x,y = queue.popleft()

        for i in range(4):
            nx,ny = x+dx[i], y+dy[i]
            if  0 <= nx < n and 0 <= ny < m and graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx,ny))

if __name__ == "__main__":
    n,m = map(int,input().split())
    graph = [list(map(int,input().rstrip())) for _ in range(n)]

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

    bfs()
    print(graph[n-1][m-1])