Pacific Atlantic Water Flow
문제
- mxn
- pacific: left & top
- atlantic: right & bottom
heights
: above sea level
- 높은 곳 -> 낮은 곳 물 흐를 수 있음
- 물이 pacific과 atlantic 모두로 흐르는 곳의 좌표 return
풀이
- bfs
- pacific에 닿아있는 지역부터 bfs -> pacific으로 흐를 수 있는 곳 True로 마킹
- atlatic에 닿아있는 지역부터 bfs -> atlantic으로 흐를 수 있는 곳 True로 마킹
- pacific과 atlantic 모두 True인 곳이 정답
- bfs 두번이면 됨
from collections import deque
class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
lenRow = len(heights)
lenCol = len(heights[0])
pacific = [[False for _ in range(lenCol)] for _ in range(lenRow)]
atlantic = [[False for _ in range(lenCol)] for _ in range(lenRow)]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
# 바다에 닿인 곳 -> 바다에 이미 접함
pacificXY = deque()
atlanticXY = deque()
for i in range(lenRow):
pacificXY.append([i, 0])
atlanticXY.append([i, lenCol-1])
for j in range(lenCol):
pacificXY.append([0, j])
atlanticXY.append([lenRow-1, j])
# pacific
visited = [[False for _ in range(lenCol)] for _ in range(lenRow)]
while pacificXY:
x, y = pacificXY.popleft()
pacific[x][y] = True
visited[x][y] = True
for i in range(4):
X = x + dx[i]
Y = y + dy[i]
if 0 <= X < lenRow and 0 <= Y < lenCol and not visited[X][Y] and heights[X][Y] >= heights[x][y]:
# 방문한 적 없고, current 높을 경우
pacificXY.append([X,Y])
visited[x][y] = True
# atlantic
visited = [[False for _ in range(lenCol)] for _ in range(lenRow)]
while atlanticXY:
x, y = atlanticXY.popleft()
atlantic[x][y] = True
visited[x][y] = True
for i in range(4):
X = x + dx[i]
Y = y + dy[i]
if 0 <= X < lenRow and 0 <= Y < lenCol and not visited[X][Y] and heights[X][Y] >= heights[x][y]:
atlanticXY.append([X,Y])
visited[x][y] = True
ans = []
for i in range(lenRow):
for j in range(lenCol):
if pacific[i][j] and atlantic[i][j]:
ans.append([i, j])
return ans
결과
heights
: above sea level- bfs
- pacific에 닿아있는 지역부터 bfs -> pacific으로 흐를 수 있는 곳 True로 마킹
- atlatic에 닿아있는 지역부터 bfs -> atlantic으로 흐를 수 있는 곳 True로 마킹
- pacific과 atlantic 모두 True인 곳이 정답
- bfs 두번이면 됨
from collections import deque
class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
lenRow = len(heights)
lenCol = len(heights[0])
pacific = [[False for _ in range(lenCol)] for _ in range(lenRow)]
atlantic = [[False for _ in range(lenCol)] for _ in range(lenRow)]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
# 바다에 닿인 곳 -> 바다에 이미 접함
pacificXY = deque()
atlanticXY = deque()
for i in range(lenRow):
pacificXY.append([i, 0])
atlanticXY.append([i, lenCol-1])
for j in range(lenCol):
pacificXY.append([0, j])
atlanticXY.append([lenRow-1, j])
# pacific
visited = [[False for _ in range(lenCol)] for _ in range(lenRow)]
while pacificXY:
x, y = pacificXY.popleft()
pacific[x][y] = True
visited[x][y] = True
for i in range(4):
X = x + dx[i]
Y = y + dy[i]
if 0 <= X < lenRow and 0 <= Y < lenCol and not visited[X][Y] and heights[X][Y] >= heights[x][y]:
# 방문한 적 없고, current 높을 경우
pacificXY.append([X,Y])
visited[x][y] = True
# atlantic
visited = [[False for _ in range(lenCol)] for _ in range(lenRow)]
while atlanticXY:
x, y = atlanticXY.popleft()
atlantic[x][y] = True
visited[x][y] = True
for i in range(4):
X = x + dx[i]
Y = y + dy[i]
if 0 <= X < lenRow and 0 <= Y < lenCol and not visited[X][Y] and heights[X][Y] >= heights[x][y]:
atlanticXY.append([X,Y])
visited[x][y] = True
ans = []
for i in range(lenRow):
for j in range(lenCol):
if pacific[i][j] and atlantic[i][j]:
ans.append([i, j])
return ans
결과
개느리네,,,,,ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
근데 solution에 있는 97% 풀이와 알고리즘은 같은데.. solution은 set으로 visited를 만들고, recursion dfs로 풀이 했다
기존 내 풀이에서 bfs를 dfs로 바꾸면 조금 더 빨라진다.
Author And Source
이 문제에 관하여(Pacific Atlantic Water Flow), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@twinklesu914/Pacific-Atlantic-Water-Flow저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)