Swim in Rising Water
모든 숫자 0부터 n²-1까지가 정확히 한 번씩 들어 있는 높이의 n × n 격자를 행 목록으로 받습니다. 비는 시간 0에 내리기 시작하고, 시간 t에는 물이 어디서나 높이 t까지 차오르므로 높이가 t 이하인 모든 칸은 물에 잠깁니다. 왼쪽 위 칸에서 시작합니다. 두 칸이 모두 물에 잠겨 있을 때 서로 변을 공유하는 칸으로 헤엄쳐 갈 수 있으며, 헤엄치는 데는 시간이 걸리지 않습니다. 오른쪽 아래 칸에 도달할 수 있는 가장 이른 시간을 반환하세요.
함수
- gridinteger-2d-array
- 높이, n개의 숫자로 이루어진 n개 행의 목록으로
- 반환값integer
- 오른쪽 아래 셀에 도달할 수 있는 가장 빠른 시간
제약 조건
n == grid.length == grid[i].length1 ≤ n ≤ 1000 ≤ grid[i][j] ≤ n²-1- 0부터
n²-1까지의 모든 값이 정확히 한 번씩 나타납니다.
예제
- 입력
- grid = [[0, 2], [3, 1]]
- 출력
- 2
- 설명
- 오른쪽 위 칸을 통과하는 경로는 0, 2, 1이며, 가장 높은 칸은 2입니다. 왼쪽 아래 칸을 통과하는 경로는 0, 3, 1이며, 가장 높은 칸은 3입니다. 시간 2에는 첫 번째 경로가 물에 잠기므로 답은 2입니다.
- 입력
- grid = [[0, 1, 2, 3, 4], [24, 23, 22, 21, 5], [12, 13, 14, 15, 16], [11, 17, 18, 19, 20], [10, 9, 8, 7, 6]]
- 출력
- 16
- 설명
- 시간 15에서는 맨 윗줄과 그 끝 아래의 5에 도달할 수 있지만, 그 구역을 빠져나가는 모든 경로는 16 이상을 거칩니다. 오른쪽을 따라 곧장 내려가면 16을 만난 다음 20에 도달합니다. 16에서 왼쪽으로 꺾어 15, 14, 13, 12, 11을 지나 맨 아랫줄을 따라 돌아가면 16보다 높은 곳으로 올라가지 않으므로 정답은 16입니다.
- 입력
- grid = [[3, 0], [1, 2]]
- 출력
- 3
- 설명
- 시작 셀의 높이는 3이므로, 시간 3이 되기 전에는 그 셀에 있을 수도, 그 셀에서 나갈 수도 없습니다. 그때쯤이면 격자 전체가 물에 잠깁니다.
제출 시 숨은 테스트 +13개
후속 질문
높이가 반복될 수 있고 10^9까지 도달한다면, 어떤 접근 방식이 여전히 변경 없이 작동하며 무엇을 대상으로 이분 탐색을 하겠습니까?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
수위가
t라는 것을 알고 있다고 가정해 봅시다. 통로가 있는지 알 수 있나요?t가 커짐에 따라 답은 어떻게 달라지나요?경로 위의 모든 셀이 물에 잠겨야 하므로, 경로에 필요한 시간은 가장 높은 셀의 높이에 따라 결정됩니다. 가장 높은 셀의 높이가 가능한 한 낮은 모퉁이 간 경로를 찾고자 합니다.
테스트로 플러드 필을 사용해
t에 대해 이진 탐색을 하거나, 셀에 도착한 시간과 셀 자체의 높이 중 더 큰 값을 해당 셀의 시간으로 설정하여 최소 힙을 사용해 다익스트라 알고리즘을 실행하세요. 오른쪽 아래 셀이 힙에서 나올 때 중단하세요.
풀이
경로에 필요한 시간은 경로에서 가장 높은 셀의 높이입니다. 지나가는 모든 셀을 물이 덮어야 하기 때문입니다. 따라서 모서리 사이의 경로 중 가장 높은 셀의 높이가 가능한 한 낮은 경로를 찾아야 합니다. 경로의 비용이 셀 높이의 합이 아니라 최댓값인 최단 경로 문제입니다. 물을 한 단계씩 높이며 테스트하거나, 같은 테스트를 이용해 수위에 대한 이진 탐색을 하거나, 가장 높은 셀을 비용으로 삼아 다익스트라 알고리즘을 실행할 수 있습니다.
물을 한 번에 한 단계씩 올리세요
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
수위 t를 정합니다. 도달할 수 있는 칸은 높이가 t 이하이고, 그런 칸들을 통해 시작점과 연결된 칸입니다. 왼쪽 위에서 한 번의 홍수 채우기를 수행하면 이 칸들을 찾을 수 있습니다. 시작점을 넣고, 칸 하나를 꺼낸 다음, 방문하지 않은 이웃 중 높이가 t 이하인 칸을 각각 넣습니다. 오른쪽 아래 칸을 방문했다면 수위 t면 충분합니다.
정답은 홍수 채우기가 도달하는 가장 작은 t입니다. 두 모서리 모두 물에 잠겨야 하므로 정답은 더 높은 모서리의 높이인 max(grid[0][0], grid[n-1][n-1])보다 낮을 수 없습니다. 그 값에서 시작해 홍수 채우기가 성공할 때까지 1씩 더합니다. 처음 성공하는 수위가 정답입니다. 물이 차오르면 칸이 열리기만 하고 닫히지는 않기 때문입니다. 성공하는 수위에서는 계속 성공합니다.
각 테스트에는 O(n²)의 비용이 들고, 도달할 때까지 수위가 거의 n²번 오를 수 있습니다. 100 × 100 격자에서는 최대 10^4개의 수위 × 10^4개의 칸으로, 약 10^8번의 칸 방문에 해당합니다. 큰 테스트에서는 모서리의 높이가 0과 1이고 정답이 4,950에서 9,998 사이이므로, 정답을 찾기 전에 수천 번의 전체 홍수 채우기가 실행됩니다.
알고리즘
t를 두 모서리 높이 중 더 높은 값으로 설정합니다.- 명시적인 스택과 각 셀의 방문 표시를 사용해 높이가
t이하인 셀을 통해 왼쪽 위에서부터 플러드 필을 수행합니다. - 플러드 필이 오른쪽 아래에 도달하면
t를 반환합니다. - 그렇지 않으면
t에 1을 더하고 다시 플러드 필을 수행합니다.
def canReach(grid, t):
# True when you can swim from the top left to the bottom right with the water at height t.
n = len(grid)
seen = [[False] * n for _ in range(n)]
seen[0][0] = True
stack = [(0, 0)]
while stack:
r, c = stack.pop()
if r == n - 1 and c == n - 1:
return True
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc] and grid[nr][nc] <= t:
seen[nr][nc] = True
stack.append((nr, nc))
return False
def swimInWater(grid):
n = len(grid)
# You cannot finish before the water covers both corners.
t = max(grid[0][0], grid[n - 1][n - 1])
# Raise the water one step at a time until a way through opens.
while not canReach(grid, t):
t += 1
return t수위에 대한 이진 탐색
핵심 아이디어
첫 번째 접근법의 테스트는 유용한 형태를 갖습니다. 정답보다 낮은 모든 레벨에서는 실패하고, 정답부터 그 이상인 모든 레벨에서는 성공합니다. 아니요에서 예로 한 번만 바뀌는 예/아니요 질문을 이진 탐색으로 찾으면 로그 횟수만큼만 시도하면 됩니다.
lo인 더 높은 모퉁이와 hi = n²-1인 가장 높은 칸 사이를 탐색합니다. 이때 전체 격자가 물에 잠겨 테스트가 성공해야 합니다. 중간 레벨을 테스트합니다. 통과하면 정답은 최대 mid이므로 hi = mid로 설정합니다. 그렇지 않으면 정답은 mid보다 높으므로 lo = mid + 1로 설정합니다. 두 값이 같아지면 그 레벨이 정답입니다.
5 × 5 예시에서 lo = 6이고 hi = 24입니다. 위쪽 영역이 막혀 있으므로 레벨 15는 실패하고, 따라서 lo = 16이 됩니다. 레벨 20, 18, 17, 16은 모두 성공하여 hi가 16까지 내려가고, 다섯 번의 플러드 필을 거쳐 탐색이 16에서 끝납니다.
100 × 100 격자에는 10^4개의 레벨이 있으므로, 약 14번의 테스트로 답을 결정할 수 있으며 각 테스트는 O(n²)입니다. 즉, 셀 방문 횟수는 약 1.4 × 10^5회로, 10^8회보다 적습니다. 플러드 필은 반복문 방식으로 구현하세요. 큰 테스트 중 하나는 길이가 약 5,000칸인 구불구불한 통로로, Python의 중첩 호출 한도인 1,000보다 훨씬 깊습니다.
알고리즘
lo를 더 높은 모서리 높이로,hi를n²-1로 설정합니다.lo < hi인 동안mid = (lo + hi) / 2를 구하고, 소수점 이하를 버립니다.- 높이
mid에서 플러드 필을 수행합니다. 오른쪽 아래에 도달하면hi = mid로 설정하고, 그렇지 않으면lo = mid + 1로 설정합니다. lo를 반환합니다.
def canReach(grid, t):
# True when you can swim from the top left to the bottom right with the water at height t.
n = len(grid)
seen = [[False] * n for _ in range(n)]
seen[0][0] = True
stack = [(0, 0)]
while stack:
r, c = stack.pop()
if r == n - 1 and c == n - 1:
return True
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc] and grid[nr][nc] <= t:
seen[nr][nc] = True
stack.append((nr, nc))
return False
def swimInWater(grid):
n = len(grid)
# The answer lies between the higher corner and the highest cell.
lo = max(grid[0][0], grid[n - 1][n - 1])
hi = n * n - 1
# canReach is false below the answer and true from it on: find the first true.
while lo < hi:
mid = (lo + hi) // 2
if canReach(grid, mid):
hi = mid
else:
lo = mid + 1
return loDijkstra를 경로의 가장 높은 칸에 적용
핵심 아이디어
격자를 그래프로 보고 각 경로에 비용을 부여하세요. 경로의 비용은 경로를 이루는 단계의 합이 아니라 가장 높은 칸의 높이입니다. 경로를 연장해도 비용이 낮아지지 않으므로 이 비용에서도 Dijkstra 알고리즘은 여전히 작동합니다. 더 긴 경로의 비용은 max(old cost, new height)이며, 기존 비용보다 낮아지지 않습니다. 이것이 Dijkstra에 필요한 유일한 성질입니다.
셀의 시간을 키로 사용하는 최소 힙을 유지하세요. 시간은 해당 셀까지 발견한 최선의 경로에서 가장 높은 셀의 높이입니다. 왼쪽 위 셀의 시간 grid[0][0]으로 시작합니다. 가장 작은 시간 t를 가진 셀을 꺼내고, 아직 방문하지 않은 각 이웃 셀에는 max(t, its height)의 시간을 부여합니다. 오른쪽 아래 셀이 힙에서 빠져나올 때 그 시간이 답입니다.
셀을 처음 넣을 때 방문한 것으로 표시해도 됩니다. 셀은 시간순으로 힙에서 빠져나오므로, 어떤 이웃에 도달하는 첫 번째 셀의 시간은 그 이웃에 도달할 다른 모든 셀의 시간보다 작거나 같습니다. 따라서 그 셀을 거쳐 도달하는 이웃의 시간이 가능한 최선입니다. 나중에 도착하는 경로의 시간은 그보다 크거나 같습니다. 그러므로 각 셀은 최종 시간으로 힙에 한 번만 들어갑니다.
이것이 단계별로 물이 차오르는 과정입니다. 힙에는 도달할 수 있는 영역의 경계가 들어 있으며, 가장 낮은 셀을 꺼내는 것은 그곳까지 이동할 수 있을 만큼 물이 정확히 차오르는 것과 같습니다. 5 × 5 예시에서 셀을 꺼내는 순서는 0, 1, 2, 3, 4, 5이며, 그다음에는 16 높이의 관문에 도달합니다. 그 뒤 돌아가는 길의 모든 셀에는 시간 16이 부여되고, 더 높은 셀이 나오기 전에 오른쪽 아래 셀이 시간 16으로 힙에서 빠져나옵니다.
n²개의 셀은 각각 최대 한 번 삽입되고 한 번 꺼내지며, 각 작업에는 O(log n)이 걸립니다. 따라서 시간 복잡도는 O(n² log n)이고, 목표 셀이 힙에서 빠져나오는 즉시 탐색을 멈춥니다.
알고리즘
- 왼쪽 위 칸을 방문한 것으로 표시하고 시간
grid[0][0]과 함께 넣습니다. - 시간이 가장 작은 칸
t를 꺼냅니다. 오른쪽 아래 칸이라면t를 반환합니다. - 아직 방문하지 않은 각 이웃 칸을 방문한 것으로 표시하고 시간
max(t, its height)와 함께 넣습니다. - 2단계부터 반복합니다.
import heapq
def swimInWater(grid):
n = len(grid)
seen = [[False] * n for _ in range(n)]
seen[0][0] = True
# (time, row, col): the time is the highest cell on the best path found to that cell.
heap = [(grid[0][0], 0, 0)]
while True:
t, r, c = heapq.heappop(heap)
# Cells leave the heap in order of time, so this is the earliest you can be here.
if r == n - 1 and c == n - 1:
return t
for nr, nc in ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1)):
if 0 <= nr < n and 0 <= nc < n and not seen[nr][nc]:
# Reached for the first time from the cell with the smallest time:
# no later route can arrive earlier, so mark it now.
seen[nr][nc] = True
heapq.heappush(heap, (max(t, grid[nr][nc]), nr, nc))
함정과 경계 사례
대부분의 오답은 놓친 구석이 있거나, 최댓값을 구해야 하는데 비용을 더하거나, 너무 일찍 탐색을 확정해서 나옵니다.
- 시작 칸 자체의 높이를 무시하는 경우. 물에 잠기기 전에는 왼쪽 위 칸에 있을 수 없으므로, 답은 최소한
grid[0][0]입니다.[[3, 0], [1, 2]]의 답은 3입니다. - 목표 칸의 높이를 무시하는 경우. 오른쪽 아래 칸도 물에 잠겨야 하므로, 답은 최소한
grid[n-1][n-1]입니다. - 현재 칸에서 가장 낮은 이웃 칸으로 그리디하게 이동하는 경우. 5 × 5 예시처럼, 최선의 경로는 관문까지 올라간 다음 멀리 돌아갈 수도 있습니다. 도달한 영역의 전체 경계를 탐색해야만 답을 찾을 수 있습니다.
- 일반적인 최단 경로처럼 경로를 따라 높이를 더하는 경우. 새 시간은
t + height가 아니라max(t, height)입니다. - 홍수 채우기에 재귀를 사용하는 경우. 구불구불한 경로는 수천 칸에 걸칠 수 있어 Python의 중첩 호출 한도인 1,000회를 초과합니다.
- 대각선으로 이동하는 경우. 현재 칸과 한 변을 공유하는 칸으로만 헤엄쳐 갈 수 있습니다.
자주 묻는 질문4
Swim in Rising Water의 시간 복잡도는 얼마인가요?
Dijkstra 알고리즘을 사용하면 O(n² log n)입니다. n²개의 각 셀은 최대 n²개의 항목을 담을 수 있는 힙에 최대 한 번 삽입되고 제거됩니다. 수위에 대한 이진 탐색도 같은 복잡도로, O(n²)인 물 채우기 작업을 약 log2(n²)번 수행합니다. 두 방법 모두 방문 여부 표시와 힙 또는 스택에 O(n²)의 메모리를 사용합니다.
비용이 가장 높은 셀일 때 Dijkstra 알고리즘은 왜 작동하나요?
Dijkstra에는 한 가지 속성이 필요합니다. 경로를 확장해도 비용이 낮아지지 않는다는 것입니다. 여기서 새 비용은 max(t, height)이며, t보다 낮아지는 경우가 없으므로 이 속성이 성립합니다. 따라서 셀이 처음 힙에서 꺼내지는 순간 그 시간이 확정되며, 목표 지점에 도달하면 탐색을 멈출 수 있습니다.
Can Swim in Rising Water는 이진 탐색으로 풀 수 있을까요?
네. 레벨 t에서 건널 수 있는지는 정답보다 낮은 모든 레벨에서는 거짓이고, 정답부터는 참입니다. t를 대상으로 이진 탐색을 하고 홍수 채우기를 검사로 사용하면 약 log2(n²)번의 검사로 답을 찾을 수 있습니다. 100 × 100 격자라면 14번입니다.
유니온 파인드로 「물에 잠기는 수위」 문제를 풀 수 있을까요?
네. 높이 순서대로 셀을 열고, 새로 연 각 셀을 인접한 열린 셀과 합친 다음, 왼쪽 위 셀과 오른쪽 아래 셀이 같은 집합에 속하는 즉시 멈추세요. 마지막으로 연 셀의 높이가 답입니다. 격자에는 n²-1까지의 모든 값이 각각 한 번씩 있으므로, 높이를 셀에 대응시키는 테이블을 사용하면 정렬하지 않고도 여는 순서를 알 수 있습니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def swimInWater(grid):
# 여기에 코드를 작성하세요케이스 1
케이스 2
케이스 3
입력
grid = [[0, 2], [3, 1]]
기대값
2