[백준/BOJ] - 2178번 python 풀이 - BFS

---

Key Point

 1. 최단거리를 구하는 문제는 bfs가 적절하다. 

 2. 시작 노드로 부터 한 다리 건너 있는 노드들의 값을 +1 씩 더해주어 최종 노드 위치의 값을 확인한다.

---

import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int,input().split())
# 한줄에 배열을 받을 수 있는 방법
arr = [list(map(int,input().rstrip())) for _ in range(n)] 
dx, dy = (-1, 1, 0, 0), (0 ,0 ,- 1, 1)

def bfs(a,b):
    q = deque()
    q.append((a,b))
    while q:
        x, y = q.popleft()
        for i in range(4):
            rx = x + dx[i]
            ry = y + dy[i]
            if (0<=rx<n) and (0<=ry<m):
                if arr[rx][ry] == 1: # 1의 의미는 이동할 수 있으며 앞서 이동하지 않은 노드 의미
                    arr[rx][ry] = arr[x][y] + 1
                    q.append((rx,ry))
bfs(0,0)
print(arr[n-1][m-1])