Baekjoon Online Judge 2178번 파이썬

문제 링크

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

2178번: 미로 탐색

 

7576번 토마토 문제와 유사하다.

앞에서 선언한 미로의 크기에서만 움직일 수 있도록 if 문을 사용하였다.

그리고 (0,0)에서 한 칸씩 나아갈 때마다 그 미로 칸의 값에 +1씩 해주어 최종적으로 마지막 칸에 도착했을 때의 값을 출력하면 얼마나 이동했는지 알 수 있다.

 

정답 코드

import sys
from collections import deque

def bfs(x,y):
  dx = [-1,1,0,0]
  dy = [0,0,-1,1]

  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 0<=nx<N and 0<=ny<M:
        if graph[nx][ny] == 1:
          graph[nx][ny] = graph[x][y] + 1
          queue.append((nx,ny))
          
  return graph[N-1][M-1] #마지막 미로 칸 값 리턴
  
graph = []
N, M = map(int,sys.stdin.readline().split())


for _ in range(N):
  graph.append(list(map(int, sys.stdin.readline().rstrip())))

print(bfs(0,0))