백준 14940번: 쉬운 최단거리 [Python]

kimminjunnn·2026년 3월 21일

백준 알고리즘

알고리즘

목록 보기

309/311

난이도 : 실버 1
문제 출처 : https://www.acmicpc.net/problem/14940

문제 파악

세로 n, 가로 m 길이의 graph가 주어진다.

graph의 값은 '0' or '1' or '2' 인데 의미는 다음과 같다.

0 : 갈 수 없는 땅
1 : 갈 수 있는 땅
2 : 목표 지점

목표는 각 지점에서 목표 지점까지의 최단 거리를 구해서 새로운 그래프로 출력하는 것이다.

단, 갈 수 없는 땅(0)은 항상 0으로 출력해야 한다.

해결 아이디어

상하좌우 탐색 + 최단거리 + 그래프 ?
=> BFS 를 떠올려야 한다.

이 때 start 노드를 각 지점의 좌표로 놓는다면 BFS를 지점의 개수만큼 돌려야 한다 -> X

start 노드를 목적지인 '2'의 값을 가지는 좌표로 두고 한번의 BFS를 돌며 그래프를 완성시켜 출력한다.

구현 포인트

1. result 배열 초기화

기본값: -1 (아직 방문 안함)
0인 칸 → 어차피 못 가니까 0
시작점(2) → 거리 0

2. BFS 조건

graph[nr][nc] == 1 (갈 수 있는 땅)
result[nr][nc] == -1 (아직 방문 안함)

갈 수 있는 땅인데? + 아직 안 간 곳
이 조건을 만족할 때만 queue에 넣고 순회

해답 및 풀이

from collections import deque
import sys
input = sys.stdin.readline

n, m = map(int,input().split())

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

graph = []

for _ in range(n):
    row = list(map(int,input().split()))
    graph.append(row)

# result 그래프 초기화 
result = [
    [-1 for _ in range(m)] for _ in range(n)
]

start = None

# 시작점 + 초기값 세팅
for i in range(n):
    for j in range(m):
        if graph[i][j] == 2:
            result[i][j] = 0
            start = (i,j)
        
        if graph[i][j] == 0:
            result[i][j] = 0

q = deque()
q.append(start)

while q:
    r,c = q.popleft()

    for d in range(4):
        nr = r + dx[d]
        nc = c + dy[d]

        if 0 <= nr < n and 0 <= nc < m:
            if graph[nr][nc] == 1 and result[nr][nc] == -1:
                result[nr][nc] = result[r][c] + 1
                q.append((nr,nc))

for row in result:
    print(*row)