[Baekjoon/Python] 14940번: 쉬운 최단거리(BFS)

# Baekjoon 14940번: 쉬운 최단거리
import sys
from collections import deque
input = sys.stdin.readline

n, m = map(int, input().split())
arr = []
sol_arr = [[None] * m for _ in range(n)]
des_x, des_y = -1, -1

for i in range(n):
    distance = list(map(int, input().split()))
    arr.append(distance)
    
    for j in range(m):
        if distance[j] == 2:
            des_x = j
            des_y = i
        elif distance[j] == 0:
            sol_arr[i][j] = 0
            
def BFS():
    sol_arr[des_y][des_x] = 0
    q = deque([(des_x, des_y)])
    
    while q:
        x, y = q.popleft()
        
        for (u, v) in [(x-1, y), (x+1, y), (x, y-1), (x, y+1)]:
            
            if 0 <= u < m and 0 <= v < n and sol_arr[v][u] is None:
                sol_arr[v][u] = sol_arr[y][x] + 1
                q.append((u, v))

BFS()

for i in range(n):
    for j in range(m):
        if sol_arr[i][j] is None:
            sol_arr[i][j] = -1

    print(" ".join(map(str, sol_arr[i])))

이 문제는 BFS 알고리즘 문제이다. BFS 알고리즘은 너비 우선 탐색으로, 특정 지점의 가장 근처에 있는 영역(이 문제에서는 상하좌우)부터 순차적으로 탐색하면서 모든 지점을 지나간다는 것이 특징이다.
먼저 입력 부분은 문제에서 주어준 지도의 데이터들을 입력 받도록 2중 for문을 활용하였다. 이때 지도 크기와 동일한 배열이면서 None으로 채워진 sol_arr을 만들었다. sol_arr은 최종 출력 배열이면서 방문여부 확인용 배열의 역할을 할 것이다.
BFS 구현 부분에서는 deque를 활용하였다. while문 안에 있는 for문을 보면 상하좌우를 탐색하도록 한 것을 볼 수 있으며, 좌표가 지도 크기 범위 내에 있으면서 방문하지 않았을 경우에만 deque에 좌표를 추가하였다.
마지막에는 아직 sol_arr에서 None인 부분을 -1로 바꾸어주었다. 이 좌표는 탐색할 수 없는 영역이다. 최종 출력은 python 내장 함수인 join 함수와 map으로 sol_arr을 str로 형변환 시킨 후 출력하였다.