[백준 문제풀이] 2178번 : 미로탐색

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

2178번: 미로 탐색

 

 

💡 앞에서 푼 문제들이 전부 DFS라 이번에도 DFS일거라 생각한 내 잘못..

미로탐색은 대부분 BFS를 사용한다.

BFS는 큐를 사용하기 때문에 파이썬 라이브러리에 있는 deque를 사용했다.

위치를 확인하기 위해 dx,dy리스트를 활용하고 각각의 위치에 기본값이 1과 0이기 때문에, 마지막 (N,M)에 바로 얼마나 이동했는지 보여주도록 만들어야 했다.

 

✔ 소스코드

from collections import deque
import sys
N,M=map(int,sys.stdin.readline().split())
matrix = [list(map(int,sys.stdin.readline().rstrip())) for _ in range(N)]

def search(x,y):
    queue=deque()
    queue.append((x,y))
    while queue:
        x,y=queue.popleft()
        dx=[+1,0,-1,0]
        dy=[0,+1,0,-1]

        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
      
            if matrix[nx][ny] == 0:
                continue

            if matrix[nx][ny] == 1:
                matrix[nx][ny] = matrix[x][y] + 1
                queue.append((nx, ny))
  
    return matrix[N-1][M-1]

print(search(0, 0))