[프로그래머스] Prim 인듯 아닌듯 Prim 같은 문제

https://school.programmers.co.kr/learn/courses/30/lessons/62050

프로그래머스

 

 

 

2차원 배열 각각의 칸은 그래프의 각 노드로 보고, 옆 칸으로 이동하는 것을 간선으로 본다

그리고 비용 없이 이동할 수 있으니까 간선의 비용을 0 으로 생각하면 된다.

이걸 왜 생각 못했냐

 

그리고 그래프를 따로 만들 필요도 없이, 인접한 좌표들에 대해 바로 heapq 에 넣어주면 된다. 

 

그래서 어차피 cost 가 0 이면 answer 에는 변함이 없으니, 계속해서 answer += cost 해주면 된다.

 

 

from heapq import *

dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]

def solution(land, height):
    answer = 0
    n = len(land)
    visited = [[False] * n for _ in range(n)]
    
    q = []
    heappush(q, (0, 0, 0))  # cost, x, y

    while q:
        cost, x, y = heappop(q)
        
        if visited[x][y]:
            continue
        
        visited[x][y] = True
        answer += cost
        
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            
            if not (0<=nx<n and 0<=ny<n):
                continue
            
            new_cost = abs(land[x][y] - land[nx][ny])
            if new_cost <= height: 
                new_cost = 0
            
            heappush(q, (new_cost, nx, ny))
    
    
    return answer