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

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

---

minheap을 사용하여 비용이 적게드는 칸으로 이동하자!

 

1. 방문여부 체크하는 visited 배열을 생성한다.
2. [비용, x좌표, y좌표]를 넣는 heap을 생성한다.
3. 방문했다면 pass하고, 안했다면 비용을 추가해준다.
4. 4방향 칸중에서 방문하지 않은 칸을 골라 height보다 차가 크다면 비용(abs(land[x][y] - land[nx][ny]))을 넣어주고, 작다면 비용을 0으로 넣어준다.

 

from collections import deque
import heapq
dx = [0, 0, -1, 1]
dy = [-1, 1, 0, 0]


def solution(land, height):
    n = len(land)
    visited = [[False]*n for _ in range(n)]
    heap = [[0, 0, 0]]
    answer = 0

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