백준 2178 미로 탐색

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

2178번: 미로 탐색

 

그냥 전형적인 bfs문제

 

bfs를 진행하면서 level까지 업데이트하고,

n-1,m-1에 도달하면, level+1을 출력

 

##코드##

from collections import deque
import sys
input=sys.stdin.readline
def bfs(i=0,j=0):
    arr[i][j]='0'
    s=deque()
    s.append([i,j,1])
    
    while s:
        i,j,v=s.popleft()
        for move in moves:
            a,b=move
            tmp_i=i+a
            tmp_j=j+b
            if 0<=tmp_i<n and 0<=tmp_j<m and arr[tmp_i][tmp_j]=='1':
                # print(tmp_i,tmp_j,v)
                if tmp_i==n-1 and tmp_j==m-1:
                    print(v+1)
                    return
                s.append([tmp_i,tmp_j,v+1])
                arr[tmp_i][tmp_j]='0'

        
n,m=map(int,input().split())
arr=[list(input().strip()) for _ in range(n)]
moves=[[-1,0],[1,0],[0,-1],[0,1]]
bfs()