[백준] 14940번,python - 쉬운 최단거리

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

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

n, m = map(int,input().split())
li = []
des_x, des_y = -1,-1
direct = [[1,0],[-1,0],[0,1],[0,-1]]

for i in range(n):
    tmp = list(map(int,input().split()))
    for j in range(m):
        if tmp[j] == 2:   # 목표지점 위치 저장
            des_x, des_y = i, j
    li.append(tmp)

# 거리 기록 배열 (-1로 초기화)
dist = [[-1]*m for _ in range(n)]

def bfs(sx,sy):
    queue = deque([(sx,sy)])
    dist[sx][sy] = 0

    while queue:
        x, y = queue.popleft()
        for dx, dy in direct:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m:
                if li[nx][ny] != 0 and dist[nx][ny] == -1: # 아직 접근 안한곳이고 접근가능한곳
                    dist[nx][ny] = dist[x][y] + 1 # 원래꺼에서 1칸 옮긴거니까 1더해줌
                    queue.append((nx,ny))

bfs(des_x, des_y)

for i in range(n):
    for j in range(m):
        if li[i][j] == 0:
            print(0, end=" ")
        else:
            print(dist[i][j], end=" ")
    print()

# 처음 풀이. bfs로 다 접근해서 시간초과뜸

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

n, m = map(int,input().split())
li = []
des_x, des_y = 0,0
direct = [[1,0],[-1,0],[0,1],[0,-1]]

for i in range(n):
    tmp = list(map(int,input().split()))
    for j in range(m):
        if tmp[j] == 2:
            des_x, des_y = i, j
    li.append(tmp)

def bfs(li,i,j):
    visited = [[False]*m for _ in range(n)]
    queue = deque([(i,j,0)])
    visited[i][j] = True

    while queue:
        x, y, cnt = queue.popleft()
        if x == des_x and y == des_y:
            return cnt

        for dx, dy in direct:
            nx, ny = x + dx, y + dy
            if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny] and li[nx][ny] != 0:
                queue.append((nx,ny,cnt+1)) # 접근 가능한 곳이면 접근 후 방문 기록
                visited[nx][ny] = True

    return -1

for i in range(n):
    for j in range(m):
        if li[i][j] == 0:
            print(0 , end =" ")
        else:
            print(bfs(li,i,j), end = " ")
    print()