[백준] 14940 쉬운 최단거리

문제

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

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

입력

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

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

출력

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

예제 입력

15 15
2 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 0 0 0 1
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1
1 1 1 1 1 1 1 1 1 1 0 1 0 0 0
1 1 1 1 1 1 1 1 1 1 0 1 1 1 1``

예제 출력

0 1 2 3 4 5 6 7 8 9 10 11 12 13 14
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
7 8 9 10 11 12 13 14 15 16 17 18 19 20 21
8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
9 10 11 12 13 14 15 16 17 18 19 20 21 22 23
10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
11 12 13 14 15 16 17 18 19 20 0 0 0 0 25
12 13 14 15 16 17 18 19 20 21 0 29 28 27 26
13 14 15 16 17 18 19 20 21 22 0 30 0 0 0
14 15 16 17 18 19 20 21 22 23 0 31 32 33 34

풀이

bfs 로 풀이했다. 이 문제는 상하좌우 4방향으로 탐색해야 한다.

값이 1인 땅을 탐색할때, 목표 지점(시작 지점)으로부터 누적 거리가 1인 경우를 다시 탐색할 우려가 있다. 따라서 누적 거리를 음수로 설정해주고, 마지막에 다시 양수로 바꿔주었다. 그러면 누적 거리가 1인 땅에 대해 -1로 표기되기 때문에 다시 탐색하지 않는다.

import sys
input = sys.stdin.readline
from collections import deque
n,m = map(int,input().split()) # 세로, 가로
arr = []
for _ in range(n): arr.append(list(map(int, input().split())))
s,e = -1,-1

for i in range(n): # 시작 지점(목표 지점) 확인
    for j in range(m):
        if arr[i][j] == 2: 
            s,e = i,j
            arr[s][e] = 0 # 목표 지점 찾은 후 0으로 설정(거리 누적합 위해)
def check(r,c):
    if r >= 0 and r < n and c >=0 and c < m and arr[r][c] == 1 and arr[r][c] != 0:
        return True
    else: return False

def bfs(r,c): # 시작 지점(=목표 지점)
    queue = deque()
    queue.append((r,c))
    
    while queue:
        r, c = queue.popleft()
        dir = [[-1,0], [0,1], [1,0],[0,-1]] # 북 동 남 서
        for d in dir:
            if check(r+d[0], c+d[1]):
                arr[r+d[0]][c+d[1]]  = arr[r][c] + 1*(-1) # 직전 누적거리 + 1 (음수 형태로)
                queue.append((r+d[0], c+d[1]))

bfs(s,e)
# 다시 양수로 바꿈
for i in range(n):
    for j in range(m):
        if j != m-1: print(arr[i][j]*(-1), end=" ")
        else: print(arr[i][j]*(-1))