[Python] 프로그래머스 지형 이동

 

 

 

문제

programmers.co.kr/learn/courses/30/lessons/62050

코딩테스트 연습 - 지형 이동

 

계속 틀려서 다른 사람의 풀이를 보고 푼 문제이다.

어떻게 이런생각을 떠올리지...?

 

heap을 사용해서 풀었다.

상,하,좌,우 칸 중에 방문하지 않은 칸과의 길이가 height보다 크다면 heap에 차이와 점을 기록한다.

height보다 작다면 0과 점을 기록한다. 이를 이용해서 min heap으로 최소한의 사다리를 건설할 수 있다.

 

 

Result

import heapq

def solution(land, height):
    
    dx=[1,-1,0,0]
    dy=[0,0,1,-1]
    n=len(land)
    visited=[[False]*n for x in range(n)]
    #시작점은 0,0 말고 아무거나 해도 됨
    h=[(0,0,0)]
    res=0
    while h:
        cnt,x,y=heapq.heappop(h) 
        
        if visited[x][y]:
            continue
            
        res+=cnt        
        visited[x][y]=True
        for i in range(4):
            xx=dx[i]+x
            yy=dy[i]+y
            #방문하지 않은 경우만 check
            if 0<=xx<n and 0<=yy<n and not visited[xx][yy]:
                temp=abs(land[x][y]-land[xx][yy])
                #height보다 차이가 크다면 그 차이를 넣어줘야함(사다리 건설비용)
                #height보다 작다면 사다리 건설비용이 들지 않기 때문에 0을 삽입
                if temp>height:
                    heapq.heappush(h,(temp,xx,yy))
                else:
                    heapq.heappush(h,(0,xx,yy))
    return res