147940번 쉬운 최단 거리

📌Problem

지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.
문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.

입력

지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)
다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다.

출력

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

✍solution

(그래프 이론)
1. 최종 목적지에서로 도달하는 것이 아닌 최종 목적지에서 출발한다고 생각하여 가능한 경로까지 가는데 걸리는 거리를 계산
2. bfs를 통해 문제 해결

💻Code

from collections import deque
def bfs(endy, endx):
    global arr
    q=deque()
    q.append([endy,endx])
    arr[endy][endx] = 2
    while q:
        y,x=q.popleft()
        for direct in [(0,-1),(0,1),(1,0),(-1,0)]:
            dy = y+direct[0]
            dx = x+direct[1]
            if dy<0 or dy>n-1 or dx<0 or dx>m-1:continue
            if arr[dy][dx]==1:
                arr[dy][dx] = arr[y][x]+1
                q.append([dy,dx])

n,m=map(int, input().split())
arr=[]
for _ in range(n):
    arr.append(list(map(int, input().split())))
for i in range(n):
    for j in range(m):
        if arr[i][j]==2:
            endy = i
            endx = j
            break
bfs(endy, endx)
for i in range(n):
    for j in range(m):
        if arr[i][j]==0:
            print(0, end=' ')
        elif arr[i][j]==1:
            print(-1, end=' ')
        else:
            print(arr[i][j]-2, end=' ')
    print('')

💡Takeaway

• visited나 used 배열을 통해 문제를 해결할 수도 있음
• 초기 값이 0과 1로 이루어져 있으므로 이미 지나간 경로를 확인하기 위해 목적지까지의 거리를 0으로 시작하는 것이 아니라 2부터 시작(arr[endy][endx] = 2)