14940: 쉬운 최단거리

• visit 2차원 리스트로 출발지점부터의 거리를 저장해둠
  visit == -1이라면 아직 방문하지 않은 노드
  -> Map == 1이라면 visit[nx][ny] = visit[x][y] + 1 (진행 가능)
  -> Map == 0이라면 visit[nx][ny] = 0 (진행 불가능)
• 히든 테케를 찾지 못해서 구글링해본 결과,
  갈 수 없는 땅은 0, 갈 수 있지만 도달할 수 없는 땅은 -1로 출력해야하는데 원래 갈 수 없는데 도달할 수 없는 땅을 -1로 출력하는 반례가 생겼음
  -> 이 부분은 마지막에 출력해줄 때 경우를 나누어서 Map이 0인 경우는 그냥 0을 출력해주도록 함

import sys
from collections import deque

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

def bfs(start_x, start_y):
	queue = deque([]); queue.append([start_x, start_y])
	visit[start_x][start_y] = 0

	while queue:
		tmp = queue.popleft(); x = tmp[0]; y = tmp[1]
		
		for i in range(4):
			nx = x + dx[i]; ny = y + dy[i]
			if nx < 0 or ny < 0 or nx >= N or ny >= M:
				continue
			if visit[nx][ny] == -1:
				if Map[nx][ny] == 1:
					visit[nx][ny] = visit[x][y] + 1
					queue.append([nx, ny])
				elif Map[nx][ny] == 0:
					visit[nx][ny] = 0

N, M = map(int, sys.stdin.readline()[:-1].split())
Map = []
for n in range(N):
	Map.append(list(map(int, sys.stdin.readline()[:-1].split())))

visit = [[-1] * M for n in range(N)]

start_x = -1; start_y = -1
for n in range(N):
	for m in range(M):
		if Map[n][m] == 2:
			start_x = n; start_y = m
			break

bfs(start_x, start_y)

for n in range(N):
	for m in range(M):
		if Map[n][m] == 0:
			print(0, end = ' ')
		else:
			print(visit[n][m], end = ' ')
	print()