[백준] 14940 쉬운 최단거리

문제

• NxM 크기의 지도에서 0은 갈 수 없는 땅, 1은 갈 수 있는 땅, 2는 목표지점이다.
• 상하좌우로만 움직일 수 있을 때, 모든 지점에 대해서 목표지점까지의 거리 구하기
• 목표지점에 도달할 수 없다면 -1 출력하기
• 1 <= N, M <= 1000

 

풀이

• 모든 지점에서 목표지점까지의 거리라는 말은, 목표지점에서 모든 지점까지의 거리라는 말과도 같다.
  따라서 목표지점에서 시작해 역으로 모든 지점까지의 거리를 계산한다.
• 갈 수 있는 지점인데 목표지점에 도달하지 못하는 경우 -1을 출력해야 하므로, 시작 전에 모든 1인 지점을 -1로 바꿔준다.
• 최단 거리를 구할 때 BFS를 사용한다.

 

from collections import deque

N, M = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]

# 목표지점 찾기 & -1로 변경
gx = gy = 0
for i in range(N) :
    for j in range(M) :
        if graph[i][j] == 1 :
            graph[i][j] = -1
        elif graph[i][j] == 2 :
            gx, gy = i, j
            graph[i][j] = 0

# 모든 지점에 대해 목표지점까지의 거리 구하기
q = deque([(gx, gy)])
visited = set({(gx, gy)})

dx = (-1, 1, 0, 0)
dy = (0, 0, -1, 1)
while q :
    x, y = q.popleft()

    for i in range(4):
        nx, ny = x+dx[i], y+dy[i]
        if 0 <= nx < N and 0 <= ny < M and graph[nx][ny] != 0 and (nx, ny) not in visited :
            graph[nx][ny] = graph[x][y] + 1
            visited.add((nx, ny))
            q.append((nx, ny))

for i in range(N) :
    print(*graph[i])

 

References

• 백준 그래프탐색