[Leetcode] 3341. Find Minimum Time to Reach Last Room I

어딘가 낯이 익은 문제여서 제출 이력을 열었더니 2024년 11월 치열하게 풀었던 흔적이 보였다.

반년이 지난 지금, 그래도 조금은 성장했나보다.

무슨 일이 있었던 것일까

 

문제 설명

n × m 크기의 던전이 있다.
이 던전은 격자 형태로 구성되어 있으며, 각 방은 상하좌우로 인접한 방으로 이동할 수 있다.

2차원 배열 moveTime이 주어진다.
moveTime[i][j]는 (i, j) 위치의 방으로 이동을 시작할 수 있는 최소 시간(초)을 의미한다.

초기 위치는 (0, 0)이며 시작 시간은 0초이다.
인접한 방으로의 이동은 항상 1초가 소요된다.

목표는 (n - 1, m - 1) 위치까지 이동하는 데 걸리는 최소 시간을 구하는 것이다.

 

예시

예제 1

입력: moveTime = [[0,4],[4,4]]

출력: 6

설명:

t = 0 → (0,0)
t = 4 → 이동 시작 → (1,0)
t = 5 → 이동 시작 → (1,1)
t = 6 도착

 

 

 

예제 2

입력: moveTime = [[0,0,0],[0,0,0]]

출력: 3

설명:

t = 0 → (0,0)
t = 1 → (1,0)
t = 2 → (1,1)
t = 3 → (1,2) 도착

 

예제 3

입력: moveTime = [[0,1],[1,2]]

출력: 3

설명:

t = 0 → (0,0)
t = 1 → (1,0)
t = 2 → (1,1)
t = 3 도착

 

조건(제약사항)

• 2 ≤ n ≤ 50
• 2 ≤ m ≤ 50
• 0 ≤ moveTime[i][j] ≤ 10⁹
• 각 이동은 오직 인접한 상하좌우 방으로만 가능하다.
• 한 방에서 여러 번 대기할 수 있다.

풀이전략

풀이 전략을 짜기 전 핵심은 특정 위치 값이 minimum_t 라면 해당 위치에 도달했을 때 시간은 minimum_t + 1 이라는 점이다.

인접한 현재 위치에서 출발을 시작해도 되는 최소 시간을 뜻하기 때문인데, 문제를 이해하는데 어려움을 주는 요소였다.

이걸 놓치면 계속 틀린 답이 나오니 주의하기.

 

1. 문제 유형 파악
   1. 이 문제는 최단 경로 문제다.
   2. 각 노드(방)에 대해 도달 가능한 시간 제한이 존재한다.
   3. 일반적인 BFS보다는 우선순위 큐를 활용한 Dijkstra 알고리즘이 적절하다.
2. 우선순위 큐 사용 (Dijkstra 방식)
   1. 각 상태를 (좌표, 시간) 구성하여, 도달 시간이 빠른 순서대로 처리한다.
   2. 다음 방으로 이동할 수 있는 최소 시간은 max(current_time + 1, moveTime[next_x][next_y] + 1)이다.
      → 현재 시간에 1초를 더한 값과, 해당 방이 허용하는 최소 시간 + 1 중 큰 값을 선택한다.
3. 방문 처리
   1. 이미 더 빠른 시간에 방문한 적이 있다면 해당 경로는 스킵한다.
4. 종료 조건
   1. (n-1, m-1)에 도달하면 즉시 해당 시간을 반환한다.

BFS 풀이 - 우선 빠르게 풀어본다

물론 BFS로도 풀 수 있다.

예상했던 Time Limit Exceed 가 뜨지는 않는다.

from collections import deque 

class Solution:
    def minTimeToReach(self, moveTime: List[List[int]]) -> int:
        n, m = len(moveTime), len(moveTime[0])
        chk = [[-1 for j in range(m)] for i in range(n)]
        moveTime[0][0], chk[0][0] = 0, 0
        q = deque()

        dr = (0, 1, 0, -1)
        dc = (1, 0, -1, 0)

        q.append((0, 0, moveTime[0][0]))
        while len(q) != 0:
            r, c, t = q.popleft()

            for i in range(4):
                nr, nc = r + dr[i], c + dc[i]

                if nr < 0 or n <= nr or nc < 0 or m <= nc:
                    continue
                if chk[nr][nc] != -1 and chk[nr][nc] <= t + 1:
                    continue
                
                chk[nr][nc] = max(t + 1, moveTime[nr][nc] + 1)
                q.append((nr, nc, chk[nr][nc]))
            
        return chk[n - 1][m - 1]

 

BFS 와 Dijkstra 알고리즘은 FIFO Queue 를 사용하느냐 Priority Queue 를 사용하느냐라고 봐도 무방하다.

혹시 이 풀이를 보기 위해 들어오신 분들은 우선순위 큐로 바꿔서 시도해보면 좋겠다.

BFS로 풀면 100명 중 95등이라는 처참한 숫자가 나온다.

BFS로 풀었을 때 결과: 하위 95%

 

Dijkstra 풀이

앞서 언급한 것처럼 Queue를 Priority Queue로 바꿔준다.

내가 Python으로 문제를 풀 때에는 heapq 모듈을 사용한다.

import heapq

class Solution:
    def minTimeToReach(self, moveTime: List[List[int]]) -> int:
        n, m = len(moveTime), len(moveTime[0])
        chk = [[-1 for j in range(m)] for i in range(n)]
        moveTime[0][0], chk[0][0] = 0, 0

        dr = (0, 1, 0, -1)
        dc = (1, 0, -1, 0)
        heap = []
        heapq.heappush(heap, (chk[0][0], (0, 0)))

        while len(heap) != 0:
            t, (r, c) = heapq.heappop(heap)

            if r == n - 1 and c == m - 1:
                return t

            for i in range(4):
                nr, nc = r + dr[i], c + dc[i]

                if nr < 0 or n <= nr or nc < 0 or m <= nc:
                    continue
                if chk[nr][nc] != -1 and chk[nr][nc] <= t + 1:
                    continue
                
                chk[nr][nc] = max(t + 1, moveTime[nr][nc] + 1)
                heapq.heappush(heap, (chk[nr][nc], (nr, nc)))
            
        return chk[n - 1][m - 1]

 

이렇게 풀어주면 적어도 50% 정도에는 드는 코드가 나온다.

BFS로 빠르게 구현 견적을 봤다면 Runtime 성능 개선을 위헤 음의 가중치가 없는 것을 확인하고, Priority Queue 로 바꿔보도록 하자.

요약(핵심)

• 이동 제한 시간이 존재하는 격자 최단 경로 문제이다.
• Dijkstra 알고리즘을 사용해 도달 가능한 최소 시간을 우선순위 큐로 관리한다.
• 다음 방으로 이동 가능한 시간은 max(현재 시간 + 1, moveTime[x][y] + 1)로 계산한다.
• 도달 지점에 도착하면 즉시 결과를 반환한다.