백준 2178 미로 탐색

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

2178번: 미로 탐색첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.www.acmicpc.net

그냥 전형적인 bfs문제

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

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

##코드##

from collections import dequeimport sysinput=sys.stdin.readlinedef 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()