[백준 14940번] 파이썬 - 쉬운 최단 거리

백준 14940_쉬운 최단거리

시간 제한 1초, 메모리 제한 128MB

# 조건

• 지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.
• 문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.

입력

• 지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)
• 다음 n개의 줄에 m개의 숫자가 주어진다.
• 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다.
• 입력에서 2는 단 한 개이다.

출력

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

# 접근 방법

• 지도를 입력받은 후 목표 지점인 2를 찾아서 기록해준다.
• 목표지점은 0이 되어야 하므로 visited 배열을 -1로 설정해준 후 원본 지도에서 0인 곳은 0으로 변경해준다.
• 목표지점부터 bfs를 돌려주며 방문 가능한 곳이면 거리를 +1씩 늘려준다.
• 또한 처음에 -1로 설정을 해두었으므로, 원래 갈 수 있는 땅이지만 도달하지 못한 곳은 그대로 -1로 출력이 된다.

import sys  
from collections import deque  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  


def bfs(si, sj):  
    global visited  
    q = deque()  
    q.append((si, sj))  
    visited[si][sj] = 0  
    while q:  
        sti, stj = q.popleft()  
        for d in range(4):  
            ni, nj = sti+di[d], stj+dj[d]  
            if 0<=ni<N and 0<=nj<M and visited[ni][nj] == -1:  
                visited[ni][nj] = visited[sti][stj] + 1  
                q.append((ni, nj))  


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

for i in range(N):  
    for k in range(M):  
        if arr[i][k] == 2:  
            si, sj = i, k  

visited = [[-1] * M for _ in range(N)]  
for i in range(N):  
    for k in range(M):  
        if arr[i][k] == 0:  
            visited[i][k] = 0  
di, dj = [1,-1,0,0], [0,0,1,-1]  
bfs(si, sj)  

for i in visited:  
    print(*i)