14940 - 쉬운 최단거리

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

14940번: 쉬운 최단거리

 

from sys import stdin
from collections import deque

input = stdin.readline
delta = [[0,1], [0,-1], [1,0], [-1,0]]


n, m = map(int, input().split())
maze = [list(map(int, input().split())) for _ in range(n)]

dept_point = tuple()

for i in range(n):
    for j in range(m):
        if maze[i][j] == 2:
            dept_point = (i, j)
            break

q = deque([dept_point])
predecessor = [[0] * m for _ in range(n)]

while q:
    k = q.pop()
    maze[k[0]][k[1]] = 2

    for dx, dy in delta:
        r = k[0] + dx
        c = k[1] + dy

        if 0 <= r < n and 0 <= c < m and maze[r][c] == 1:
            q.appendleft((r,c))
            maze[r][c] = 2
            predecessor[r][c] = predecessor[k[0]][k[1]] + 1

for i in range(n):
    for j in range(m):
        if maze[i][j] == 0:
            print(0, end=" ")
        else:
            if predecessor[i][j] == 0 and maze[i][j] != 2:
                print(-1, end=" ")
            else:
                print(predecessor[i][j], end=" ")
    print()

 

방금 포스팅했던 SWEA 6일차 - 미로의 거리와 거의 유사한 문제이다! 여기서는 그냥 predecessor 리스트를 거의 그대로 출력해주게 바꾸기만 해줘도 정답이 된다~