[백준] 14940 쉬운 최단거리 - python

문제 링크

이 문제는 bfs로 푸는 문제이다.
근데 이 문제에서 결과로 출력하는 부분이 잘 이해가 가지 않아서 헤맸다.

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

여기서 갈 수 없는 땅이라기에 그냥 도달할 수 없는 땅을 의미하는 줄 알았는데 땅이 0이라서 지나갈 수 없는 땅을 이야기하는 것이었다.

그래서 이 부분을 출력할 때, graph가 0이면 0을 출력하도록 수정하였더니, 해결되었다.

# 쉬운 최단거리
import sys
from collections import deque

n, m = map(int, sys.stdin.readline().rstrip().split(' '))

graph = []
for i in range(n):
    temp = list(map(int, sys.stdin.readline().rstrip().split(' ')))
    graph.append(temp)
    
visited = [[-1]*m for _ in range(n)]

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

def bfs(i, j):
    queue = deque()
    queue.append((i, j))
    visited[i][j] = 0
    while queue:
        x, y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < m and visited[nx][ny] == -1:
                if graph[nx][ny] == 0:
                    visited[nx][ny] = 0
                elif graph[nx][ny] == 1:
                    visited[nx][ny] = visited[x][y] + 1
                    queue.append((nx, ny))

for i in range(n):
    for j in range(m):
        if graph[i][j] == 2 and visited[i][j] == -1:
            bfs(i, j)

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

일반적인 bfs를 통한 문제 풀이와 다른 것은 visited의 기본값을 Fasle로 설정하는 것이 아니라 -1로 설정한다는 것, 그리고 노드를 통과하면 visited를 이전 노드의 visited 값의 +1로 설정한다는 것이다.