
https://leetcode.com/problems/swim-in-rising-water/
Swim in Rising Water - LeetCode
Level up your coding skills and quickly land a job. This is the best place to expand your knowledge and get prepared for your next interview.
leetcode.com
- (0, 0)에서 (N-1, N-1)로 가는 최단 거리를 찾는 전형적인 다익스트라 알고리즘 문제
풀이
import heapq
class Solution(object):
def swimInWater(self, grid):
N = len(grid)
visit = set()
minH = [[grid[0][0], 0, 0]] # (time/mx-height, r, c)
dir = [[0, 1], [0, -1], [1, 0], [-1, 0]]
visit.add((0, 0))
# 다익스트라 알고리즘 사용
while minH:
t, r, c = heapq.heappop(minH)
if r == N-1 and c == N-1:
return t
for dr, dc in dir:
nr, nc = r + dr, c + dc
if 0 <= nr < N and 0 <= nc < N and (nr, nc) not in visit:
visit.add((nr, nc))
heapq.heappush(minH, [max(t, grid[nr][nc]), nr, nc])
'리트코드' 카테고리의 다른 글
리트코드 130 Surrounded Regions (파이썬) (0) | 2022.10.23 |
---|---|
리트코드 1584 Min Cost to Connect All Points (파이썬) (0) | 2022.10.10 |
리트코드 684 Redundant Connection (파이썬) (0) | 2022.10.09 |
리트코드 79 Word Search (파이썬) (0) | 2022.10.09 |
리트코드 417 Pacific Atlantic Water Flow (파이썬) (0) | 2022.10.09 |