[백준/Python] Silver I #14940 쉬운 최단거리

14940번: 쉬운 최단거리

문제

지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.

문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.

입력

지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)

다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다.

출력

각 지점에서 목표지점까지의 거리를 출력한다. 원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다.

풀이

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

n,m = map(int,input().split())
li = [list(map(int,input().split())) for _ in range(n)]
visited = [[False] * m for _ in range(n)]
ans = [[-1] * m for _ in range(n)]
queue = deque([])

dx = [1,-1,0,0]
dy = [0,0,1,-1]

for i in range(n):
  for j in range(m):
    if li[i][j] == 2:
      queue.append((i,j))
      visited[i][j] = True
      ans[i][j] = 0
    if li[i][j] == 0:
      ans[i][j] = 0

while queue:
  x, y = queue.popleft()
  for i in range(4):
    nx = x+dx[i]
    ny = y+dy[i]
    if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny] and li[nx][ny] == 1:
      queue.append((nx,ny))
      visited[nx][ny] = True
      ans[nx][ny] = ans[x][y] + 1

for i in range(n):
  for j in range(m):
    print(ans[i][j],end=' ')
  print()