[프로그래머스] - 지형 이동 (LEVEL4)

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

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

 처음에는 각각의 그룹 sets 를 만들어내고, 각 sets[i]마다 다시 사다리를 만드는 비용이 최소로 드는 지점을 탐색하는 식으로 코드를 짰지만 시간초과.

 

 지형간의 높이 차가 cost라고 했을 때, height >= cost 일 경우에는, 비용이 0이라는 점, 최소 비용문제라는 점을 생각해보면 heapq로 풀 수 있는 문제였다.

 

<Solution>

 

from heapq import *
def solution(land, height):
    answer = 0
    n=len(land)
    v=[[0]*n for _ in range(n)]
    q=[]; heappush(q,(0,0,0))
    while q:    
        c,x,y=heappop(q)
        if v[y][x]: continue
        v[y][x]=1
        answer+=c
        for dx,dy in [[-1,0],[1,0],[0,1],[0,-1]]:
            nx,ny=x+dx,y+dy
            if 0<=nx<n and 0<=ny<n and v[ny][nx]==0:
                cost = abs(land[y][x]-land[ny][nx])
                if cost>height: heappush(q,(cost,nx,ny))
                else: heappush(q,(0,nx,ny))
    return answer