[Graph: Dijkstra] 778. Swim in Rising Water ★★★

778. Swim in Rising Water

 

You are given an n x n integer matrix grid where each value grid[i][j] represents the elevation at that point (i, j).
👉 n x n 정수 행렬 grid가 주어지며, grid[i][j]는 (i, j) 지점의 **고도(elevation)**를 나타냅니다.
The rain starts to fall.
👉 비가 내리기 시작합니다.
At time t, the depth of the water everywhere is t.
👉 시간 t가 되면, 모든 지점의 물 깊이는 t입니다.
You can swim from a square to another 4-directionally adjacent square if and only if the elevation of both squares individually are at most t.
👉 한 칸에서 상하좌우 인접한 칸으로 수영할 수 있는 조건은, 그 두 칸의 고도 각각이 현재 시간 t 이하여야 합니다.
You can swim infinite distances in zero time.
👉 한 번의 수영은 시간 소요 없이 무한 거리를 이동할 수 있습니다. (다만 조건을 만족하는 칸들만 가능함)
Of course, you must stay within the boundaries of the grid during your swim.
👉 물론 수영할 때는 그리드 바깥으로 나가면 안 됩니다.
Return the least time until you can reach the bottom right square (n - 1, n - 1) if you start at the top left square (0, 0).
👉 (0, 0)에서 시작해서 (n-1, n-1) 지점에 도달할 수 있는 최소 시간을 반환하세요.

 

이 문제는 LeetCode의 유명한 문제인 "Swim in Rising Water" 입니다.
비유하자면 "물이 점점 차오르는 진흙탕에서 탈출하는 퍼즐" 같은 문제예요.
천천히 핵심을 설명드릴게요! 🌊

---

🧩 문제 상황 요약

• grid는 n x n 정수 배열이고, 각 칸은 **고도(elevation)**를 뜻해요.
  • 예: grid[0][0] = 0, grid[1][2] = 5 → 고도가 낮을수록 쉽게 이동 가능.
• 비가 계속 와서 시간이 t가 될수록 물 깊이도 t가 돼요.
  • 고도 3인 땅은 t = 3이 되어야 물에 잠겨서 수영 가능.
• 수영은 인접한 4방향으로만 가능 (상하좌우).
  • 단, 이동하려는 두 칸 모두의 고도 ≤ 현재 시간 t여야 수영할 수 있어요.
• 목표:
  (0, 0)에서 시작해서 (n-1, n-1)까지 도달할 수 있는 최소 시간 t를 구하세요.

---

📌 중요한 조건 요약

• t시간일 때, 고도 ≤ t인 칸만 지나갈 수 있어요.
• 이동은 4방향으로만 가능.
• 한번 움직일 때 시간은 들지 않지만, 물이 충분히 찰 때까지 기다려야 함.

---

📷 예시

 

grid = [ [0, 2], [1, 3] ]

• 시작: (0, 0) 고도 0
• 도착: (1, 1) 고도 3

이동 경로 (가능한 시간 기준):

1. t = 0: (0,0)만 접근 가능
2. t = 1: (1,0) 접근 가능 → 고도 1
3. t = 2: (0,1) 가능 → 고도 2
4. t = 3: (1,1) 가능 → 고도 3

→ 최소 시간은 3이 되어야 끝에 도달할 수 있어요.

---

🧠 핵심 아이디어 (풀이 전략)

✅ 우선순위 큐 + BFS (Dijkstra 비슷)

• 매번 고도가 가장 낮은 칸부터 탐색하면서 퍼져 나갑니다.
• (0,0)부터 시작해서, 현재까지 거쳐온 칸들 중 고도 최댓값을 추적합니다.
• 도착점 (n-1,n-1)에 도달하면, 그때까지 거쳐온 경로의 최댓값이 최소 시간입니다.

---

🚀 시간복잡도

• O(n^2 log n) (우선순위 큐 사용)

import heapq
from typing import List

class Solution:
    def swimInWater(self, grid: List[List[int]]) -> int:
        N = len(grid)
        directions = [[1,0], [-1,0], [0,1], [0, -1]]
        visit = set()

        minheap = [[grid[0][0], 0, 0]] # grid value 고도(elevation), r, c
        visit.add((0, 0)) # r, c

        while minheap:
            t, r, c = heapq.heappop(minheap)

            # 도착지점에 도달하면
            if r == N-1 and c == N-1:
                return t

            for dr, dc in directions:
                nr, nc = dr+r, dc+c

                # 그리드 벗어나거나, 이미 방문했으면 skip
                if not (0<=nr<N and 0<=nc<N and (nr, nc) not in visit):
                    continue

                """
                아래 코드는 "지금 물 깊이 t보다 더 높은 곳은 못 가니까 거르자" 라는 의미인데
                아래와 같이 하면 안됨
                if t <= grid[nr][nc]:
                    # 이웃좌표 방문 표시
                    visit.add((nr, nc))

                    # 현재까지 잠긴 최고 고도값 기록하면서 이동
                    heapq.heappush(minheap, [grid[nr][nc], nr, nc])

                “언젠가 도달 가능할 경로까지 미리 탐색큐에 넣어두는 것”
                즉, grid[nr][nc]가 지금 t보다 크더라도,
                우리는 그 칸이 언젠가 방문 가능하다는 사실을 알고 큐에 넣는 거예요.
                또한, 우선순위 큐가 그 경로 중 가장 물이 적게 찬(최소 시간인) 경로부터 꺼내서 처리해 줌
                따라서, 

                # 현재까지 잠긴 최고 고도값 기록하면서 이동 하면 됨
                heapq.heappush(minheap, [max(t, grid[nr][nc]), nr, nc])
                """                
                # 이웃좌표 방문 표시
                visit.add((nr, nc))

                # 🔹 이웃 노드로 이동하는 데 걸리는 최소 시간을 업데이트
                # 🔹 지금까지의 시간 t와 다음 칸의 고도 중 큰 값이 그 칸에 도달하는 데 걸리는 최소 시간
                heapq.heappush(minheap, [max(t, grid[nr][nc]), nr, nc])