[백준] 2178번 미로 탐색, 최단거리 BFS (Python3)

문제 설명

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

나의 풀이

최단거리를 구하는 문제 ! ==> BFS !!!

'다음 구간의 거리 == 현재구간까지의 거리 + 1' 을 명심하자!!

BFS : 큐에서 하나씩 꺼내면서 그 노드와 연결된 모든 노드를 큐에 삽입 -> 반복

import sys

N, M = map(int,sys.stdin.readline().split())

global matrix
matrix = [[0]*M for _ in range(N)]
visited = [[0]*M for _ in range(N)] # 0 : 가지 않은 곳, 0이 아닌 수 : 거리

for i in range(N):
    input_maps = sys.stdin.readline()
    for j in range(M):
        matrix[i][j] = int(input_maps[j])

def bfs(i, j):
    queue.append([i,j])

    visited[i][j] = 1
    while len(queue) > 0:
        a, b = queue.pop(0)

        for direction in range(4): # 네 방향에 대하여
            goX = a+x[direction]
            goY = b+y[direction]
            if 0 <= goX < N and 0 <= goY < M:
                if visited[goX][goY] == 0 and matrix[goX][goY] == 1:
                    visited[goX][goY] = visited[a][b]+1 # 다음 거리는리현재 거리 + 1
                    queue.append([goX, goY])

# 좌 우 아래 위
x = [0, 0, 1, -1]
y = [-1, 1, 0, 0]

queue = []
answer = []

bfs(0, 0)

print(visited[N-1][M-1])