[백준]14940번: 쉬운 최단거리

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

14940번: 쉬운 최단거리

---

목표지점을 시작점으로 하여, 모든 지점까지의 거리를 구해서 출력하면 된다.

 

"원래 갈 수 없는 땅인 위치는 0을 출력하고, 원래 갈 수 있는 땅인 부분 중에서 도달할 수 없는 위치는 -1을 출력한다." 라는 조건만 잘 보면 될 것 같다.

 

python

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

n, m = map(int, input().split())
table = []
for _ in range(n):
  table.append( list(map(int,input().split())) )

visited = [[0 for j in range(m)] for i in range(n)]
dx = [-1,0,1,0]
dy = [0,1,0,-1]

def bfs(x,y):
  q = deque()
  q.append((x,y))

  visited[x][y] = 1
  
  while q:
    x,y = q.popleft()
      
    for i in range(4):
      nx = x + dx[i]
      ny = y + dy[i]

      if 0<=nx<n and 0<=ny<m and visited[nx][ny]==0:
        if table[nx][ny] == 0:
          visited[nx][ny] = 1
        elif table[nx][ny] == 1:
          visited[nx][ny] = visited[x][y] + 1
          q.append((nx,ny))

# 목표지점에서 bfs
for i in range(n):
  for j in range(m):
    if table[i][j] == 2:
      bfs(i,j)

# 결과 출력
for i in range(n):
  for j in range(m):
    if table[i][j] == 0:
      print(0,end=' ')
    else:
      print(visited[i][j]-1, end=' ')
  print()