[Silver I] 쉬운 최단거리 - 14940 (BFS)

문제

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

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

입력

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

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

출력

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

 

풀이 방법

모든 지점에서 목표지점까지 거리를 구하기 위해서 각 지점마다 BFS 알고리즘을 사용하게 된다면 시간초과가 난다. 그러나, 모든 지점마다 구해야하기 때문에 최대한 시간을 줄일 방법을 생각해내야 한다.

반대로 생각해서 목표지점을 기준으로 시작해서 BFS 알고리즘을 사용하여 거리를 하나씩 기록해주면 해결된다.

 

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

n, m = map(int,input().split())
graph = []
answer = [[-1 for _ in range(m)] for _ in range(n)]
visited = [[False for _ in range(m)] for _ in range(n)]
dx, dy = (1,-1,0,0), (0,0,1,-1)
  
for i in range(n):
  graph.append(list(map(int,input().split())))
for i in range(n):
  for j in range(m):
    if graph[i][j] == 0 or graph[i][j] == 2:
      answer[i][j] = 0
      visited[i][j] = True
      if graph[i][j] == 2:
        q = deque()
        q.append((i,j))
      
while q:
  x, y = q.popleft()
  for i in range(4):
    nx, ny = dx[i] + x, dy[i] + y
    if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
      visited[nx][ny] = True
      answer[nx][ny] = answer[x][y] + 1
      q.append((nx,ny))
for i in range(n):
  print(*answer[i])