문제 설명
m × n 크기의 2차원 행렬 heights가 있다고 가정해 봅시다. heights[i][j]는 셀 (i, j)의 높이를 나타냅니다. 우리는 왼쪽 위 셀인 (0, 0)에서 출발하여 오른쪽 아래 끝 셀인 (m-1, n-1)까지 이동하려고 하며, 상·하·좌·우 네 방향으로 자유롭게 움직일 수 있습니다. 여기서 '경로의 노력(effort)'이란 경로상에서 연속된 두 셀 사이 높이 차이의 절댓값 중 최댓값을 의미합니다. 따라서 목적지에 도달하는 데 필요한 노력의 최솟값을 구하는 것이 이 문제의 목표입니다.
예시
입력이 다음과 같다고 해보겠습니다.
| 2 | 3 | 4 |
| 4 | 9 | 5 |
| 6 | 4 | 6 |
이때 출력은 1입니다. 경로 [2, 3, 4, 5, 6]를 따라 이동할 때 인접한 셀 간의 높이 차 절댓값이 최대 1이기 때문입니다.
해결 접근 방식
이 문제는 최단 경로 탐색에 널리 쓰이는 다익스트라(Dijkstra) 알고리즘을 응용하면 효율적으로 해결할 수 있습니다. 파이썬의 heapq 모듈은 최소 힙(min-heap) 기반 우선순위 큐를 제공하므로, 누적 노력이 가장 적은 셀부터 우선적으로 탐색할 수 있습니다. 전체 진행 과정은 다음과 같습니다.
- r := 행렬의 행 개수, c := 열 개수
- queue := 초기 튜플 (0, 0, 0)을 담은 우선순위 큐
- 큐가 빌 때까지 다음을 반복합니다.
- cur := 큐에서 노력 값이 가장 작은 항목을 꺼냄
- c_eff := cur[0], x := cur[1], y := cur[2]
- (x, y)가 도착점(r-1, c-1)이면 c_eff를 반환
- heights[x][y]가 빈 문자열(이미 방문한 셀)이면 다음 반복으로 건너뜀
- 네 방향 [[1,0], [-1,0], [0,1], [0,-1]]에 대해:
- newx := x + dx, newy := y + dy
- 새 좌표가 행렬 범위 내에 있고 아직 방문하지 않았다면, eff := max(c_eff, |heights[newx][newy] - heights[x][y]|)를 계산한 뒤 (eff, newx, newy)를 큐에 삽입
- 탐색을 마친 현재 셀은 방문 처리(heights[x][y] := "")
핵심 아이디어는 다익스트라 알고리즘과 동일합니다. 노력 값이 가장 작은 경로부터 먼저 확장하기 때문에, 도착점을 처음 큐에서 꺼내는 순간의 노력 값이 곧 정답이 됩니다.
구현 예제
아래 파이썬 코드로 실제 동작을 확인해 볼 수 있습니다.
import heapq
def solve(heights):
r,c=len(heights),len(heights[0])
queue=[(0,0,0)]
while queue:
cur=heapq.heappop(queue)
c_eff=cur[0]
x=cur[1]
y=cur[2]
if x==r-1 and y==c-1:
return c_eff
if heights[x][y]=="":
continue
for dx,dy in [[1,0],[-1,0],[0,1],[0,-1]]:
newx=x+dx
newy=y+dy
if 0<=newx
입력
[[2,3,4],[4,9,5],[6,4,6]]
출력
1
복잡도 분석
모든 셀은 최대 한 번씩 확장되며, 힙 연산 하나당 O(log V)의 시간이 소요됩니다. 따라서 셀의 개수를 V = m × n이라 할 때 전체 시간 복잡도는 O(V log V)이고, 공간 복잡도 역시 O(V)입니다.