사용자 도구

사이트 도구


ps:problems:programmers:62050

지형 이동

ps
링크https://programmers.co.kr/learn/courses/30/lessons/62050
출처프로그래머스
문제 번호62050
문제명지형 이동
레벨Level 4
분류

그래프, 최소 신장 트리

시간복잡도O(N^2*logN)
인풋사이즈N<=300
사용한 언어Python
해결날짜2020/12/11

풀이

  • 전체가 연결되도록 사다리를 설치한다는 말을 바꾸면, 모든 인접 격자간에 사다리가 있는 상태에서 전체가 연결되도록 최소한만 남기고 철거한다고 볼수도 있다
  • 각 격자가 노드가 되고, 인접 격자간에 엣지가 존재하는 그래프를 만들고, 거기서 최소 신장 트리를 구하면 끝
    • 엣지의 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)

토론

댓글을 입력하세요:
R Y M D F
 
ps/problems/programmers/62050.txt · 마지막으로 수정됨: 2021/01/22 14:53 저자 teferi