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

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

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

이동하는 것은 dfs와 최소 비용 사다리는 heapq를 활용해서 풀었다

dfs + heapq

 

알고리즘

1. 0, 0 에서 방문 가능한 곳 방문(height)

2. height 차 때문에 방문 못하면 height차이와 x , y 를 heapq에 저장

3. 이동 할 수 있는 곳 모두 이동 했을 때, 전체를 모두 방문했는지 확인

4. 전체를 모두 방문하지 않았으면 가장 비용이 적은 사다리를 heapq.heappop()을 통해 추가

5. x , y 부터 다시 방문하며 찾음

 

나의 풀이

import heapq
import sys
sys.setrecursionlimit(10**9)
visited_count = 0

def dfs(x,y,visited,land,height,ladder):
    global visited_count
    moves = [(1,0),(-1,0),(0,1),(0,-1)]
    visited[x][y] = 1
    visited_count += 1
    for move in moves:
        dx, dy = move
        next_x, next_y = x + dx, y + dy
        if next_x < 0 or next_x >= len(land) or next_y < 0 or next_y >= len(land):
            continue
        if visited[next_x][next_y] == 0:
            if abs(land[x][y]-land[next_x][next_y]) <= height:
                visited, ladder = dfs(next_x,next_y,visited,land,height,ladder)
            else:
                heapq.heappush(ladder,[abs(land[x][y]-land[next_x][next_y]),next_x,next_y])
    return visited, ladder

def solution(land,height):
    global visited_count
    answer = 0
    land_count = len(land)**2
    visited = [[0]*len(land[0]) for _ in range(len(land))]
    ladder = []
    visited, ladder = dfs(0,0,visited,land,height,ladder)
    while land_count != visited_count:
        cost, x, y = heapq.heappop(ladder)
        if visited[x][y] == 1:
            continue
        else:
            answer += cost
            visited, ladder = dfs(x,y,visited,land,height,ladder)
    return answer