https://programmers.co.kr/learn/courses/30/lessons/1844

Problem

(0,0)좌표에서 시작해 (N,M)으로 갈수 있는 최소 거리를 구하는 문제

Solution

BFS를 이용해서 (0,0)=>(N,M)의 최솟값 구하기

코드설명

1)(0,0)을 큐에 넣기
2)큐에서 하나씩 뽑아 상하좌우값에서 방문을 안했고 그 값이면 큐에 넣어주기
3) 큐에 넣으면서 방문처리와 배열상 값을 더해주기
4)마지막 값 출력

Python Code

import sys
from collections import deque
N,M=map(int,sys.stdin.readline().split())

arrList=[]
dx=[-1,0,1,0]
dy=[0,-1,0,1]
visited=[[False]*M for _ in range(N)]

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


queue=deque([(0,0)])

while queue:
    tmpy,tmpx=queue.popleft()
    visited[tmpy][tmpx]=True

    for i in range(4):
        tmpyy=tmpy+dy[i]
        tmpyx=tmpx+dx[i]

        if tmpyy<0 or tmpyx<0 or tmpyy>N-1 or tmpyx>M-1:
            continue

        if not visited[tmpyy][tmpyx] and arrList[tmpyy][tmpyx]==1:
            arrList[tmpyy][tmpyx]=arrList[tmpy][tmpx]+1
            queue.append((tmpyy,tmpyx))
print(arrList[N-1][M-1])