백준 / 14940번 / 쉬운 최단거리 / python 파이썬

 

문제 : https://www.acmicpc.net/problem/14940

 

 

코드 

from collections import deque

n, m = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]
distance = [[-1] * m for _ in range(n)]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def bfs(i, j):
    q = deque([(i, j)])
    distance[i][j] = 0

    while q:
        x, y = q.popleft()
        for d in range(4):
            nx, ny = dx[d] + x, dy[d] + y

            if 0 <= nx < n and 0 <= ny < m and distance[nx][ny] == -1:
                if grid[nx][ny] == 1:
                    distance[nx][ny] = distance[x][y] + 1
                    q.append((nx, ny))
                elif grid[nx][ny] == 0:
                    distance[nx][ny] = 0

for i in range(n):
    for j in range(m):
        if grid[i][j] == 2:
            bfs(i, j)

for i in range(n):
    for j in range(m):
        if grid[i][j] == 0:
            print(0, end=' ')
        else:
            print(distance[i][j], end=' ')
    print()

 

BFS로 접근하여 풀 수 있다. 하지만 원래 갈 수 없는 위치는 0을, 원래 갈 수 있는 땅 중 도달할 수 없는 위치는 -1로 구별하여 출력해야 한다. 그러므로 distance를 -1로 초기화함으로써  거리가 업데이트되지 않은 위치는 여전히 -1로 남아 있게 되어, 해당 위치가 탐색되지 않았음을 나타낼 수 있다.