[boj] 백준 14940 쉬운 최단거리 python 풀이

문제

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

14940번: 쉬운 최단거리

 

 

문제 풀이

0인 부분만 잘 세팅해주면 되는 bfs 문제

 

코드

import sys
input = sys.stdin.readline
import collections

N, M = map(int,input().split())
MAP = []
res = [[-1 for _ in range(M)] for _ in range(N)]
for i in range(N):
    tmp = list(map(int,input().split()))    
    for j in range(M):
        if tmp[j] == 2:
            target_x, target_y = i, j
        if tmp[j] == 0:
            res[i][j] = 0
    MAP.append(tmp)
    
move = {(-1,0),(0,1),(1,0),(0,-1)}
q = collections.deque()
q.append((target_x, target_y,0))
MAP[target_x][target_y] = -1 # visited
res[target_x][target_y] = 0 # target

while q:
    cx, cy, cnt = q.popleft()

    for tx, ty in move:
        nx = tx + cx
        ny = ty + cy

        if 0<=nx<N and 0<=ny<M and MAP[nx][ny] == 1:
            res[nx][ny] = cnt+1
            MAP[nx][ny] = -1
            q.append((nx,ny,cnt+1))

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