14940. 쉬운 최단거리

업데이트 시간 : 2025-06-27 10:21:16 +0000

[Silver I] 쉬운 최단거리 - 14940

문제 링크

성능 요약

메모리: 41868 KB, 시간: 408 ms

분류

그래프 이론, 그래프 탐색, 너비 우선 탐색, 격자 그래프

제출 일자

2025년 6월 27일 19:21:02

문제 설명

지도가 주어지면 모든 지점에 대해서 목표지점까지의 거리를 구하여라.

문제를 쉽게 만들기 위해 오직 가로와 세로로만 움직일 수 있다고 하자.

입력

지도의 크기 n과 m이 주어진다. n은 세로의 크기, m은 가로의 크기다.(2 ≤ n ≤ 1000, 2 ≤ m ≤ 1000)

다음 n개의 줄에 m개의 숫자가 주어진다. 0은 갈 수 없는 땅이고 1은 갈 수 있는 땅, 2는 목표지점이다. 입력에서 2는 단 한개이다.

출력

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

💡 Solutions

📄 쉬운 최단거리.py

import sys
input = sys.stdin.readline

from collections import deque


n, m= map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(n)]
rlt =[[-1 for _ in range(m)] for _ in range(n)]

def bfs(a, b):
    
    d = ((0,-1), (0,1), (-1,0), (1,0))
    que = deque([(a,b, 0)])
    rlt[a][b] = 0
    
    while que:
        x, y, depth = que.popleft()
        
        for dx, dy in d:
            nx = x + dx
            ny = y + dy
            
            if not (0 <= nx < n and 0 <= ny < m) : continue
            if matrix[nx][ny] == 0 : continue
            if rlt[nx][ny] != -1 : continue
            
            rlt[nx][ny] = depth + 1
            que.append((nx,ny, rlt[nx][ny]))

for i in range(n):
    for j in range(m):
        if matrix[i][j] == 0:
            rlt[i][j] = 0
        elif matrix[i][j] == 2:
            bfs(i,j)
            
for i in range(n):
    print(*rlt[i])