# 테페리넷

## 테페리넷

### 관리자 전용

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

### 문서 도구 