Swim in Rising Water
n × n 높이 격자가 주어지며, 이 격자에는 0부터 n²-1까지의 모든 숫자가 정확히 한 번씩 들어 있습니다. 시간 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에는 첫 번째 경로가 물에 잠깁니다.
- 입력
- 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에서 시작해 15, 14, 13, 12, 11을 지나 맨 아래 행으로 돌아가도 16을 넘지 않습니다.
- 입력
- grid = [[3, 0], [1, 2]]
- 출력
- 3
- 설명
- 시작 셀의 높이는 3이므로, 시간 3 이전에는 그 셀에 있을 수도, 그 셀을 떠날 수도 없습니다. 그때쯤이면 격자 전체가 물에 잠깁니다.
후속 질문
높이가 반복될 수 있고 10^9까지 커질 수 있다면, 어떤 접근 방식이 여전히 그대로 작동하며 무엇을 대상으로 이진 탐색을 하시겠습니까?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
수위
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번의 칸 방문이 발생합니다.
알고리즘
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수위에서의 이진 탐색
핵심 아이디어
플러드 필 테스트는 정답보다 낮은 모든 레벨에서 실패하고, 정답부터 그 이후의 모든 레벨에서 성공합니다. 이진 탐색은 더 높은 모서리와 n²-1 사이에서 전체 격자가 물에 잠기는 전환점을 찾습니다.
5 × 5 예시에서 lo = 6이고 hi = 24입니다. 레벨 15에서 실패하므로 lo = 16이 됩니다. 레벨 20, 18, 17, 16은 모두 성공하고, 다섯 번의 채우기 후 탐색은 16에서 끝납니다.
100 × 100 격자에는 10^4개의 레벨이 있으므로, 약 14번의 채우기로 답을 결정합니다. 즉, 10^8번 대신 약 1.4 × 10^5번의 셀 방문이 필요합니다.
알고리즘
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 lo경로에서 가장 높은 셀에 대한 다익스트라
핵심 아이디어
각 경로에 비용을 부여하세요. 경로에서 가장 높은 칸의 높이가 비용입니다. 높이가 h인 칸까지 경로를 확장하는 비용은 max(old cost, h)이며, 기존 비용보다 작아지지 않으므로 다익스트라 알고리즘은 여전히 작동합니다. 각 칸을 해당 시간으로 정렬하는 최소 힙에 넣고, 왼쪽 위 칸의 시간 grid[0][0]에서 시작하세요. 오른쪽 아래 칸이 힙에서 나올 때의 시간이 정답입니다.
칸을 처음 넣을 때 방문한 것으로 표시할 수 있습니다. 칸은 시간 순서대로 힙에서 나오므로, 이웃 칸에 도달하는 첫 번째 칸이 그 이웃에 도달할 수 있는 가장 작은 시간을 보장하며, 각 칸은 힙에 한 번만 들어갑니다.
힙에는 도달할 수 있는 영역의 가장자리가 들어 있으며, 항목을 꺼낼 때마다 그곳으로 이동하는 데 필요한 만큼만 물이 차오릅니다. 5 × 5 예시에서는 항목을 꺼낼 때의 값이 0, 1, 2, 3, 4, 5 순서로 이어지다가 16에 있는 관문에 도달하고, 오른쪽 아래 칸은 16일 때 나옵니다.
알고리즘
- 왼쪽 위를 방문한 것으로 표시하고 시간
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]과grid[n-1][n-1]입니다.[[3, 0], [1, 2]]의 경우 답은 3입니다. - 가장 낮은 이웃 칸으로 탐욕적으로 이동하기. 5 × 5 예시처럼 가장 좋은 경로는 관문까지 올라간 다음 먼 길을 돌아갈 수도 있습니다.
- 일반적인 최단 경로처럼 경로의 높이를 더하기. 새로운 시간은
t + height가 아니라max(t, height)입니다. - 플러드 필에 재귀 사용하기. 구불구불한 경로는 수천 개의 칸을 지날 수 있어 Python의 중첩 호출 제한인 1,000회를 초과하게 됩니다.
자주 묻는 질문3
Swim in Rising Water의 시간 복잡도는 얼마인가요?
Dijkstra 알고리즘을 사용하면 O(n² log n)입니다. n²개의 셀 각각은 힙에 최대 한 번 삽입되고 한 번 꺼내집니다. 수위에 대해 이진 탐색을 하면 동일한 상한을 가지며, O(n²)인 플러드 필을 약 log2(n²)회 수행합니다. 두 방법 모두 O(n²)의 메모리를 사용합니다.
Can Swim in Rising Water는 이진 탐색으로 풀 수 있나요?
네. 레벨 t에서 건널 수 있는지는 답에서 false에서 true로 한 번 바뀝니다. 테스트로 flood fill을 사용하는 이진 탐색으로 t를 탐색하면 약 log2(n²)번의 flood fill이 필요하며, 100 × 100 격자에서는 14번입니다.
유니온 파인드로 「물에 잠기는 수영」 문제를 풀 수 있을까요?
네. 높이 순서대로 셀을 열고, 새로 연 각 셀을 열려 있는 이웃 셀과 합친 다음, 두 모서리가 같은 집합에 속하는 즉시 멈추세요. 마지막으로 연 셀의 높이가 정답입니다. n²-1까지의 각 값이 한 번씩 나타나므로, 높이에서 셀로 대응하는 표를 만들면 정렬하지 않고도 순서를 알 수 있습니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
def swimInWater(grid):
# 여기에 코드를 작성하세요테스트 #1
테스트 #2
테스트 #3
인자
grid = [[0, 2], [3, 1]]
예상 출력
2