[Leetcode] 3342. Find Minimum Time to Reach Last Room II

문제를 열어보고 아직 하루가 안 지났나? 라는 생각을 했다.

다행히 자세히 확인해보니 아래 문구가 추가되어 있었다.

 

Moving between adjacent rooms takes one second for one move and two seconds for the next, 
alternating between the two.
: 이동할 때마다 1초, 2초를 번갈아 가며 더해준다.

* alternating: 번갈아가며

 

그러니 어제 풀이를 그대로 가져와, 더해주는 1s 와 2s 를 번갈아가도록 바꿔만 주면 될 것 같았다.

이동이 전제되어 있으니 좌표 값의 짝수/홀수 여부가 더해주는 시간과 대응하는 사실을 이용하기만 하면 될 것 같았다.

결과는 성공이었다.

 

 

자세한 풀이는 아래 포스팅을 참고해보자.

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

 

문제 설명

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

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

초기 위치는 (0, 0)이며 시작 시간은 0초이다.
인접한 방으로의 이동은 1초, 2초를 번갈아가며 소요한다.

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

 

예시

예제 1

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

출력: 7

설명:

t = 0 → (0,0)
t = 4 → 이동 시작 (1초 소요) → (1,0) 
t = 5 → 이동 시작 (2초 소요) → (1,1)
t = 7 도착

 

예제 2

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

출력: 6

설명:

t == 0, (0, 0) → (1, 0) in one second.
t == 1, (1, 0) → (1, 1) in two seconds.
t == 3, (1, 1) → (1, 2) in one second.
t == 4, (1, 2) → (1, 3) in two seconds.

 

 

조건(제약사항)

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

풀이전략

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

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

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

 

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

Dijkstra 풀이

이전 풀이에서 하나만 추가했다.

공짜로 문제 하나 먹었다.

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)

            add_point = (r + c) % 2

            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 + add_point:
                    continue
                
                chk[nr][nc] = max(t + 1 + add_point, moveTime[nr][nc] + 1 + add_point)
                heapq.heappush(heap, (chk[nr][nc], (nr, nc)))
            
        return chk[n - 1][m - 1]

 

요약(핵심)

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