백준 2178번 파이썬 문제풀이(큐와 그래프 - 미로탐색) - BFS

---

위 문제는 0,0 부터 좌표를 한칸씩 이동하면서 이동할 수 있는 부분에 전의 횟수에서 +1씩 하면 되는 문제이다. 0,0에서 이동할 수있는 위치는 (1,0), (0,1) 이기 때문에 그 값을 1에서 2로 바꿔준다. 또 (1,0)에서 이동할 수 있는 위치 (1,1),(2,0),는 또 2에서 +1값인 3으로 바꿔준다. 이런식으로 쭉쭉 N,M 까지의 좌표를 찾아가다 보면 움직이는 최소값을 금방 찾을 수 있다.  

import sys
from collections import deque

input = sys.stdin.readline

N, M = map(int, input().split())

graph = []  # 입력받을 그래프를 담을 리스트 선언

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

# 한 점을 기준으로 (위 아래 왼쪽 오른쪽) 으로 한칸 씩 이동할 좌표 설정
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]


def bfs(a, b):
    queue = deque()
    queue.append([a, b])

    while queue:
        x, y = queue.popleft()

        for i in range(4):
            nx = x + dx[i]  # 행값
            ny = y + dy[i]  # 열값

            if nx >= N or ny >= M or nx < 0 or ny < 0:
                continue

            if graph[nx][ny] == 1:
                graph[nx][ny] = graph[x][y] + 1
                queue.append([nx, ny])

    return graph[N - 1][M - 1]


print(bfs(0, 0))