지형 이동

• 전체가 연결되도록 사다리를 설치한다는 말을 바꾸면, 모든 인접 격자간에 사다리가 있는 상태에서 전체가 연결되도록 최소한만 남기고 철거한다고 볼수도 있다
  • 이렇게 생각하면 바로 최소 신장 트리 (Minimum Spanning Tree / MST) 문제라고 이해할 수 있다.
• 각 격자가 노드가 되고, 인접 격자간에 엣지가 존재하는 그래프를 만들고, 거기서 최소 신장 트리를 구하면 끝
  • 엣지의 weight가 사다리의 비용이다. 높이차가 height이하면 0, 아니면 높이차.
• 시간 복잡도는
  • 그래프를 생성하는 데 걸리는 시간은 격자 갯수만큼이니까 O(N^2).
  • MST를 찾는 시간은 프림 알고리즘을 사용하므로 O(ElogV)이고, V=N*N, E=O(2*V)니까 결국 O(N^2*logN)
  • 두개 더하면 최종적으로 O(N^2*logN)

"""Solution code for "Programmers 62050. 지형 이동".

- Problem link: https://programmers.co.kr/learn/courses/30/lessons/62050
- Solution link: http://www.teferi.net/ps/problems/programmers/62050
"""

from teflib import tgraph


def solution(land, height):
    size = len(land)
    wgraph = [{} for _ in range(size * size)]
    for r in range(size):
        for c in range(size):
            n = r * size + c
            if c < size - 1:
                diff = abs(land[r][c] - land[r][c + 1])
                cost = (0 if diff <= height else diff)
                wgraph[n][n + 1] = wgraph[n + 1][n] = cost
            if r < size - 1:
                diff = abs(land[r][c] - land[r + 1][c])
                cost = (0 if diff <= height else diff)
                wgraph[n][n + size] = wgraph[n + size][n] = cost

    return tgraph.minimum_spanning_tree(wgraph)

• Dependency: teflib.tgraph.minimum_spanning_tree