title: "[프로그래머스] 지형 이동 Python 파이썬 해설 (Level 4) - 이도훈"
cleanUrl: "programmers/62050"
description: "프로그래머스 Level 4 문제 [지형 이동]의 풀이를 정리합니다."

문제 설명 및 제한사항

아이디어 및 해결 방법

차근차근 생각해보면 BFS와 MST를 써서 해결 가능한 문제임을 알 수 있습니다. 아이디어를 떠올리는 순서를 요약하면

1. 사다리 없이 이동 가능한 구획들을 먼저 BFS로 파악 후 구분해봅니다. (높이 차이가 ≤ height 인 지점만 이동 가능)
2. 이제 구획 간에 사다리를 두어야 하는데, 어떤 두 구획 A와 B 사이에 사다리를 둘 수 있는 위치는 무척 많습니다. 최소 비용을 달성하려면, 그중에 어디에 사다리를 두어야 될까요? 당연히 A와 B가 인접한 위치 중 높이 차이가 가장 작은 위치가 될 것입니다.
3. 이를 활용하여 인접하고 있는 모든 구획들의 쌍에 대해 사다리를 ‘둘 수 있는’ (최소 비용의) 위치를 파악해 두고, 그 위치에 사다리를 두었을 때 발생하는 비용을 cost로 같이 저장해 둡니다.
4. 이제 이 상황은 ‘구획’들을 노드로, 사다리를 둘 수 있는 위치와 비용을 edge cost로 하는 그래프로 생각해볼 수 있고, 모든 구획들을 방문할 수 있도록 최소 비용으로 사다리를 두는 문제는 MST로 생각해볼 수 있습니다.
5. 프림 알고리즘을 써서 MST를 구현한 뒤 cost의 합을 리턴하면 됩니다.

코드

from collections import deque, defaultdict
from heapq import heappush, heappop

def solution(land, height):
    R, C = len(land), len(land[0])
    # bfs로 사다리 없이 이동 가능한
    # 위치들의 그룹을 파악합니다
    groupid, groupmap = 0, dict()
    vis = set()
    for r in range(R):
        for c in range(C):
            if (r, c) in vis:
                continue
            
            # BFS를 1회 돌립니다.
            q = deque()
            q.append( (r, c) )
            vis.add( (r, c) )
            groupmap[(r, c)] = groupid
            while q:
                r1, c1 = q.popleft()
                
                for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                    if 0 <= r1+dr < R and 0 <= c1+dc < C:
                        if (r1+dr, c1+dc) in vis:
                            continue
                        
                        if abs(land[r1+dr][c1+dc] - land[r1][c1]) > height:
                            continue
                        
                        q.append( (r1+dr, c1+dc) )
                        vis.add( (r1+dr, c1+dc) )
                        groupmap[(r1+dr, c1+dc)] = groupid
            
            groupid += 1
            
    # 그룹 수가 1개면 0을 리턴합니다.
    if set(groupmap.values()) == 1:
        return 0
    
    # 그룹 사이의 높이 차가 최소인 지점을 edge weight로
    # 둔 그래프를 하나 만듭니다.
    weightmap = {}
    for r in range(R):
        for c in range(C):
            for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
                
                if 0 <= r+dr < R and 0 <= c+dc < C:
                    g1, g2 = groupmap[(r, c)], groupmap[(r+dr, c+dc)]
                    g1, g2 = min(g1, g2), max(g1, g2)
                    if g1 == g2:
                        continue
                    
                    w = abs(land[r][c] - land[r+dr][c+dc])
                    weightmap[(g1, g2)] = min(weightmap.get((g1, g2), w), w)
                    
    G = defaultdict(list)
    for (u, v), w in weightmap.items():
        G[u].append((v, w))
        G[v].append((u, w))
    
    # 그룹 그래프에서 mst를 찾아 edge weight 합의
    # 최솟값을 리턴하면 됩니다.
    q = []
    answer = 0
    vis = set()
    heappush(q, (0, 0))
    
    while q:
        cost, u = heappop(q)
        if u in vis:
            continue
        
        vis.add(u)
        answer += cost
        
        for v, w in G[u]:
            if v in vis:
                continue
            
            heappush( q, (w, v) )
    
    return answer

출처

프로그래머스 코딩테스트 연습 https://school.programmers.co.kr/learn/challenges