[알고리즘] 프로그래머스 - 지형 이동

프로그래머스 - 지형 이동

실패한 내 풀이

import heapq
import sys

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


def solution(land, height):
    answer = 0
    visited = [[sys.maxsize]*len(land[0]) for _ in range(len(land))]
    def search(y, x):
        heap = []
        heapq.heappush(heap, (0, y, x)) # cost, y, x
        visited[0][0] = 0
        while heap:
            cost, y, x = heapq.heappop(heap)
            for i in range(4):
                ny, nx = y + dy[i], x + dx[i]
                if 0<= ny < len(land) and 0<= nx < len(land[0]):
                    if visited[ny][nx] == sys.maxsize:
                        if abs(land[y][x] - land[ny][nx]) <= height:
                            visited[ny][nx] = visited[y][x]
                        else:
                            visited[ny][nx] = abs(land[y][x] - land[ny][nx])
                        heapq.heappush(heap, (land[ny][nx], ny, nx))

                    else: # 방문했던 경우
                        if abs(land[y][x] - land[ny][nx]) <= height: # 사다리 필요 없는 경우
                            if visited[y][x] < visited[ny][nx]:
                                visited[ny][nx] = visited[y][x]
                                heapq.heappush(heap, (visited[ny][nx], ny, nx))
                        else:
                            if visited[y][x] + 2 < visited[ny][nx]:
                                visited[ny][nx] = abs(land[y][x] - land[ny][nx])
                                heapq.heappush(heap, (visited[ny][nx], ny, nx))


    search(0,0)
    ans = set()
    for i in range(len(land)):
        for j in range(len(land[0])):
            ans.add(visited[i][j])
            # print(visited[i][j], end= " ")
    #     print()
    # print()
    return sum(ans)


print(solution([[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]], 3), 15)
print(solution([[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]], 1), 18)

수정한 내 코드

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


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

    heap = []
    heapq.heappush(heap, (0, 0, 0)) # cost, y, x
    value = 0

    while heap:
        cost, y, x = heapq.heappop(heap)
        if visited[y][x]:
            continue

        visited[y][x] = True
        value += cost

        for i in range(4):
            ny, nx = y + dy[i], x + dx[i]
            if 0 <= ny < len(land) and 0 <= nx < len(land[0]):
                if abs(land[y][x] - land[ny][nx]) <= height:
                    heapq.heappush(heap, (0, ny, nx))
                else:
                    heapq.heappush(heap, (abs(land[y][x] - land[ny][nx]), ny, nx))

    return value

여기 보고 이해하고 코드 수정함