문제 보기 · Level 4 · Summer/Winter Coding(2019) · 정답률 20% · 푼 사람 2,167명 (2026-09-30 기준)1

문제

N×N 격자 칸마다 높이가 있다. 상하좌우로 이웃한 칸의 높이 차가 height 이하면 그냥 오갈 수 있다. 더 크면 사다리를 놓아야 하고, 비용은 두 칸의 높이 차다. 아무 칸에서 출발해 모든 칸을 방문할 수 있게 하는 사다리 비용의 최솟값을 돌려준다.

  • 4 ≤ N ≤ 300, 높이 1 ~ 10,000
  • 1 ≤ height ≤ 10,000

풀이

막히면 한 단계씩 펼친다.

필요한 개념
  • 최소 신장 트리: 칸을 점, 이웃을 간선으로 보고, 그냥 오갈 수 있는 간선은 비용 0, 아니면 높이 차를 비용으로 두면, 답은 이 그래프의 최소 신장 트리 비용이다.
  • 너비 우선 탐색(BFS): 사다리 없이 오갈 수 있는 칸끼리 묶는 다른 풀이에 쓴다.
1단계 · 작은 예로 손으로 풀기

예시 1(height = 3)

 1  4  8 10
 5  5  5  5
10 10 10 10
10 10 10 20

사다리 없이 오갈 수 있는 칸끼리 묶으면 세 무리다. 위 두 줄(1 → 4 → 5 → 8 → 10 식으로 이어진다), 아래 두 줄의 10들, 오른쪽 아래 20 하나다.

“이웃이고 높이 차가 3 이하”라는 관계만으로는 무리를 정할 수 없다. 맨 왼쪽 위 1과 바로 아래 5는 차가 4라 바로는 못 가지만, 1 → 4 → 5 → 5로 돌아가면 닿는다(추이성이 없다). 그래서 무리는 “이어 가며 닿는가”로 정한다. 이 관계는 동치관계라서 칸들을 겹치지 않게 나눈다.

무리끼리는 사다리가 있어야 한다. 위 무리와 가운데 무리 사이 가장 싼 사다리는 5 ↔ 10으로 5, 가운데와 20 사이는 10 ↔ 20으로 10이다. 합은 15다.

2단계 · 가장 단순한 방법과 그 속도

놓을 사다리의 조합을 모두 해 보면 가짓수가 폭발한다. “모든 칸을 이으면서 비용 합이 가장 작은 간선 모음”은 최소 신장 트리 그 자체라, 그 알고리즘을 쓰면 된다. 비용이 모두 0 이상이라, 고른 간선에 사이클이 있으면 그 사이클의 간선 하나를 빼도 모든 칸이 그대로 이어지고 비용은 늘지 않는다. 그래서 가장 싼 답 중에는 늘 신장 트리가 있고, 그 간선은 N² − 1개다.

3단계 · 핵심 아이디어
  • 그래프로 바꾸기: 칸 N²개가 점이다. 이웃 두 칸 사이 간선의 비용은 높이 차가 height 이하면 0, 아니면 높이 차다.
  • 최소 신장 트리: 모든 칸이 이어지게 간선을 골라 비용 합을 최소로 = 최소 신장 트리. 비용 0인 간선은 사다리가 필요 없는 이동이다.
  • 프림으로: 간선을 미리 만들지 않고, (0, 0)에서 시작해 “지금까지 이은 칸”에 붙은 간선을 힙에 넣고 가장 싼 것부터 새 칸을 붙인다. 비용 0인 이웃이 먼저 붙으니, 한 무리를 다 붙인 뒤에야 사다리를 쓴다.
4단계 · 코드 흐름
  1. 힙에 (0, 0, 0)을 넣는다(비용, 행, 열).
  2. 힙에서 가장 싼 것을 꺼낸다. 이미 붙인 칸이면 버린다. 아니면 붙이고 비용을 더한다.
  3. 그 칸의 이웃 중 아직 안 붙인 칸마다 (비용, 칸)을 힙에 넣는다. 비용은 높이 차 ≤ height면 0, 아니면 높이 차다.
  4. 힙이 빌 때까지 되풀이하고 비용 합을 돌려준다.
5단계 · 파이썬 코드 
import heapq

def solution(land, height):
    N = len(land)
    seen = [[False] * N for _ in range(N)]
    heap = [(0, 0, 0)]                        # (이 칸을 붙이는 비용, 행, 열)
    total = 0
    while heap:
        w, r, c = heapq.heappop(heap)
        if seen[r][c]:
            continue
        seen[r][c] = True
        total += w
        for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
            nr, nc = r + dr, c + dc
            if 0 <= nr < N and 0 <= nc < N and not seen[nr][nc]:
                diff = abs(land[r][c] - land[nr][nc])
                heapq.heappush(heap, (0 if diff <= height else diff, nr, nc))
    return total
  • 같은 칸이 힙에 여러 번 들어갈 수 있다. 처음 꺼낸 것이 가장 싼 값이니, 이미 붙인 칸은 꺼낼 때 버린다.
  • 다익스트라와 모양이 비슷하지만, 힙에 넣는 값이 “출발점부터의 합”이 아니라 “이 간선 하나의 비용”이다. 이것이 최소 신장 트리(프림)다.
6단계 · 실행 추적

예시 1을 무리로 보면(0부터 센 번호)

0 0 0 0
0 0 0 0
1 1 1 1
1 1 1 2
무리 사이 가장 싼 사다리 고름
0 – 1 5 ↔ 10, 비용 5 고름
1 – 2 10 ↔ 20, 비용 10 고름

프림은 (0, 0)에서 시작해 비용 0인 칸으로 무리 0을 먼저 다 붙이고, 5짜리 사다리로 무리 1로 넘어가 다 붙인 뒤, 10짜리 사다리로 20을 붙인다. 합은 15다.

7단계 · 복잡도와 흔한 실수

칸 V = N², 간선 약 2V개에 힙을 써서 \(O(V \log V)\)다. 300×300으로 재 보니 0.2초가 안 걸렸다.

  • 다익스트라처럼 힙에 “누적 비용”을 넣는다. 그러면 출발점에서 먼 칸일수록 비싸져 답이 커진다.
  • 무리를 BFS로 나누고 무리 사이 사다리를 아무것이나 고른다. 무리 사이 간선 중 싼 것부터, 고리가 생기지 않게 골라야 한다(크루스칼).
  • 높이 차가 정확히 height인 경우를 사다리가 필요한 것으로 센다. “이하”면 그냥 오간다.
검증: 문제의 예시 2개를 통과했고, 6단계의 무리 지도와 무리 사이 사다리를 코드로 확인했다. 2×2·3×3 땅 300개에서 “칸 그래프의 모든 신장 트리 중 가장 싼 것”과, 4×4 ~ 8×8 땅 500개에서 “BFS로 무리를 묶고 크루스칼을 돌리는” 풀이와 결과가 같았다. 300×300의 시간도 쟀다 — 28_pg62050_p1.py

  1. 프로그래머스 스쿨, “지형 이동” (https://school.programmers.co.kr/learn/courses/30/lessons/62050), 2026-09-30 조회. ↩