프로그래머스 - 지형 이동 [Summer / Winter Coding (2019)]

문제 설명:

N x N 크기인 정사각 격자 형태의 지형이 있습니다. 각 격자 칸은 1 x 1 크기이며, 숫자가 하나씩 적혀있습니다. 격자 칸에 적힌 숫자는 그 칸의 높이를 나타냅니다.

이 지형의 아무 칸에서나 출발해 모든 칸을 방문하는 탐험을 떠나려 합니다. 칸을 이동할 때는 상, 하, 좌, 우로 한 칸씩 이동할 수 있는데, 현재 칸과 이동하려는 칸의 높이 차가 height 이하여야 합니다. 높이 차가 height 보다 많이 나는 경우에는 사다리를 설치해서 이동할 수 있습니다. 이때, 사다리를 설치하는데 두 격자 칸의 높이차만큼 비용이 듭니다. 따라서, 최대한 적은 비용이 들도록 사다리를 설치해서 모든 칸으로 이동 가능하도록 해야 합니다. 설치할 수 있는 사다리 개수에 제한은 없으며, 설치한 사다리는 철거하지 않습니다.

각 격자칸의 높이가 담긴 2차원 배열 land와 이동 가능한 최대 높이차 height가 매개변수로 주어질 때, 모든 칸을 방문하기 위해 필요한 사다리 설치 비용의 최솟값을 return 하도록 solution 함수를 완성해 주세요.

---

문제 예시:

land	height	result
[[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]]	3	15
[[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]]	1	18

 

입출력 예 #1

예시 1 - 지형 이동

위 그림에서 사다리를 이용하지 않고 이동 가능한 범위는 같은 색으로 칠해져 있습니다. 예를 들어 (1행 2열) 높이 4인 칸에서 (1행 3열) 높이 8인 칸으로 직접 이동할 수는 없지만, 높이가 5인 칸을 이용하면 사다리를 사용하지 않고 이동할 수 있습니다.

따라서 다음과 같이 사다리 두 개만 설치하면 모든 칸을 방문할 수 있고 최소 비용은 15가 됩니다.

높이 5인 칸 → 높이 10인 칸 : 비용 5
높이 10인 칸 → 높이 20인 칸 : 비용 10

---

문제 해결:

from collections import deque
import heapq

def move2(y, x, N, visited):
    if not (0 <= y < N and 0 <= x < N):
        return False
    if visited[y][x]:
        return False
    return True

def solution(land, height):
    n = len(land)
    
    visited = [[False for _ in range(n)] for _ in range(n)]
    d = [(0,1), (0,-1), (1,0), (-1,0)]
    q = []
    
    q.append((0, 0, 0))
    visit_count = 0
    max_count = n*n
    value = 0
    
    while(visit_count < max_count):
        v, y, x = heapq.heappop(q)
        if visited[y][x]:
            continue
        
        visited[y][x] = True
        
        visit_count += 1
        value += v
        
        c_h = land[y][x]
        for dy, dx in d:
            ny, nx = y+dy, x+dx
            
            if move2(ny, nx, n, visited):
                n_h = land[ny][nx]
                
                if abs(n_h - c_h) > height:
                    heapq.heappush(q, (abs(n_h - c_h), ny, nx))
                else:
                    heapq.heappush(q, (0, ny, nx))
    
    return value

이 문제는 스스로 풀다가 시간에 쫓겨서 풀지 못한 문제이다.

코드의 원문은 Reference를 봐주면 좋겠다.

답변을 보고 이해한 대로 풀어내는 설명이며 질문은 환영이다.

 

먼저 각 지형의 구역을 나누는 것에 집중하기보단 전체를 다 도는 bfs, dfs를 적용한다

이때 queue에 넣는 값은 다음과 같다 (v, y, x)

1. 맨 처음에 (0, 0, 0)을 넣은 이유는 v에 사다리를 놓아야 하는 경우에만 값을 넣기로 결정하였으며 이는 아래에서 나온다.

2. 따라서, while문은 visit_count < max_count로 전체를 다 돈다

3. 이후, visited의 true, false의 유무에 따라서 continue 인지 아닌지 결정된다.

4. 그 이후, value에는 v를 더해주고 visit_count도 하나씩 늘려줘서 추후에 while이 성공적으로 끝날 수 있게 한다.

5. move2라는 함수는 dx, dy를 더한 다음 값이 맞는지 아닌지 확인하기 위한 함수이며

6. c_h의 경우 current height이다

7. 이후, max_height보다 크면 (n_h - c_h), 사다리를 놓아야 하므로 v에 뺀 값을 넣는다.

8. 그렇지 않은 경우에는 넣지 않는다.

9. 그리고 최종으로 value를 넣는다.

 

중요 포인트: Heap을 사용하면 v가 작은 순서대로 값이 앞으로 가며 heappop을 하게 되면 맨 처음 index가 튀어나오니 자연스럽게 최솟값만 더할 수 있게 된다.

---

Referece: https://ysyblog.tistory.com/105