LeetCode의 417번째 문제인 Pacific Atlantic Water Flow를 함께 풀어보도록 하겠습니다.
문제
m x n 크기의 직사각형 섬이 태평양과 대서양에 모두 접해 있습니다.
태평양은 섬의 좌측과 상단 가장자리와 접촉하며, 대서양은 섬의 우측과 하단 가장자리와 접촉합니다.
이 섬은 정사각형 칸(cell)의 행렬(grid)로 분할되어 있습니다.
m x n 정수 행렬 heights가 주어지며, heights[r][c]는 좌표 (r, c)은 칸의 해수면 위의 높이를 나타냅니다.
이 섬은 많은 비가 내리며, 비가 현재 칸의 높이보다 작거나 같은 경우 주변 칸로 직접 북쪽, 남쪽, 동쪽 및 서쪽으로 흐를 수 있습니다. 그리고 해양에 인접한 어떤 칸에서든 해양으로 흐를 수 있습니다.
(ri, ci)칸로 부터 비가 태평양과 대서양 양쪽으로 흐를 수 있음을 result[i] = [ri, ci]으로 나타내는 이차원 배열을 result를 반환하시오.
예제
Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]Input: heights = [[1,2,2,3,5],[3,2,3,4,4],[2,4,5,3,1],[6,7,1,4,5],[5,1,1,2,4]]
Output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]]풀이 1
이 문제를 푸는 가장 단순 무식한 방법은 주어진 이차원 배열 내의 각 섬에서 비가 흐를 수 있는 모든 경로를 따져보는 것입니다.
각 섬을 그래프의 정점(vertex)라고 생각하고, 좌우아래에 있는 섬 중에서 높이가 작거나 동일한 섬과 간선(edge)이 있다고 상상해보세요. 그러면 각 섬에서 그래프 탐색을 시작하면 비가 태평양(Pacific Ocean)과 대서양(Atlantic Ocean)으로 흐르는지를 알아낼 수 있을 것입니다.
예를 들어, 2번째 열의 4번째 행에 있는 섬에서 비가 흐를 수 있는 모든 경로를 수를 찾아보면 다음과 같은데요.
(1, 3)
(1, 2)
(1, 1)
(0, 1)🅿️
(0, 2)🅿️
(1, 4)🅰️
(0, 3)🅿️
(2, 3)
(2, 4)🅰️태평양으로 비가 흐를 수 있는 경로가 3가지이고, 대서양으로 비가 흐를 수 있는 경로가 2가지입니다.
따라서 우리는 (1, 3) 위치에 있는 섬에서는 비가 태평양과 대서양 양쪽으로 흐를 수 있다는 것을 알 수 있습니다.
또 다른 예로, 3번째 열의 3번째 행에 있는 섬에 대해서 생각해볼까요?
(2, 2)
(2, 1)
(2, 0)🅿️
(1, 1)
(0, 1)🅿️
(2, 3)
(2, 4)🅰️
(1, 2)
(1, 1)
(0, 1)🅿️
(0, 2)🅿️
(3, 2)
(4, 2)🅰️이번에는 태평양으로 비가 흐를 수 있는 경로가 4가지이고, 대서양으로 비가 흐를 수 있는 경로가 2가지입니다.
따라서 마찬가지로 우리는 (2, 2) 위치에 있는 섬에서는 비가 태평양과 대서양 양쪽으로 흐를 수 있다는 것을 알 수 있습니다.
반면에 4번째 행의 4번째 열에 있는 섬에서 비가 흐를 수 있는 모든 경로를 따져보면, 이번에는 대서양으로만 비가 흐를 수 있다는 것을 알 수 있습니다.
(3, 3)
(3, 2)
(4, 2)🅰️
(2, 3)
(2, 4)🅰️
(4, 3)🅰️마찬가지로 2번째 행의 2번째 열에 있는 섬에서 비가 흐를 수 잇는 모든 경로를 생각해보면, 태평야으로만 비가 흐를 수 있다는 것을 알 수 있습니다.
(1, 1)
(0, 1)🅿️그럼 이 알고리즘을 깊이 우선 탐색을 이용하여 코드로 작성해볼까요? 태평양으로 비가 흐를 수 있는 섬과 대서양으로 비가 흐를 수 있는 섬을 각각 다른 재귀 함수로 구현하였습니다.
class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
n_rows, n_cols = len(heights), len(heights[0])
def dfs_pac(row, col, visited):
if (row, col) in visited:
return False
visited.add((row, col))
if row == 0 or col == 0:
return True
for r, c in [
(row, col - 1),
(row, col + 1),
(row - 1, col),
(row + 1, col),
]:
if 0 <= r < n_rows and 0 <= c < n_cols:
if heights[row][col] >= heights[r][c]:
if dfs_pac(r, c, visited):
return True
return False
def dfs_atl(row, col, visited):
if (row, col) in visited:
return False
visited.add((row, col))
if row == n_rows - 1 or col == n_cols - 1:
return True
for r, c in [
(row, col - 1),
(row, col + 1),
(row - 1, col),
(row + 1, col),
]:
if 0 <= r < n_rows and 0 <= c < n_cols:
if heights[row][col] >= heights[r][c]:
if dfs_atl(r, c, visited):
return True
return False
result = []
for row in range(n_rows):
for col in range(n_cols):
if dfs_pac(row, col, set()) and dfs_atl(row, col, set()):
result.append((row, col))
return result입력 배열의 행의 수를 r 열의 수를 n이라고 했을 때, 모든 섬에 대해서 두 번의 깊이 우선 탐색이 일어나므로 이 풀이의 시간 복잡도는 O((r * c)^2)이 됩니다.
공간 복잡도는 재귀 호출 스택의 깊이가 그래프의 최대 깊이와 비례하므로 O(r * c)이 됩니다.
풀이 2
살짝 발상을 전환하여 그래프 탐색을 반대 방향으로 해보는 것은 어떨까요?
각 섬에서 바다로 물이 흘러내려올 수 있을지를 생각하는 것이 아니라, 반대로 바다에서 각 섬으로 물이 흘러올라갈 수 있는지를 생각해보는 거에요.
이렇게 접근하면 필요한 그래프 탐색의 양을 획기적으로 줄일 수 있는데요. 왜냐하면 바다에 닿고 있는 가장자리에 있는 섬에 대해서만 탐색을 시작해도 되기 때문입니다.
기본 아이디어는 가장자리에 있는 각 섬에서 바닷물이 출발하여 홀러올라갈 수 있는 모든 섬을 중복 없이 찾는 것입니다. 우선 좌측과 상단 가장자리 섬에서는 태평양 물이 흘러올라갈 수 있는 유일한 섬들을 찾고, 다음으로 우측과 하단 가장자리 섬에서는 대서양 물이 흘러올가갈 수 있는 유일한 섬들을 찾습니다. 최종적으로 이 두 개의 그룹에 모두 속하는 섬이 우리가 찾고자 하는 섬들이 되겠죠?
이해를 돕기 위해서 깊이 우선 탐색 과정을 한 번 시각화해보겠습니다. ✅은 새로운 섬을 찾았다는 것을 나타내고, ❌은 중복되는 섬을 찾았다는 것을 나타냅니다.
우선 태평양과 접하는 좌측 가장자리 섬들을 위에서 부터 아래로 새로 방향 탐색합니다. 태평양으로 물가 흐를 수 있는 13개의 섬을 찾을 수 있습니다.
(0, 0)✅
(1, 0)✅
(0, 1)✅
(1, 1)✅
(2, 1)✅
(3, 1)✅
(2, 2)✅
(0, 1)❌
(1, 2)✅
(2, 2)❌
(1, 3)✅
(1, 4)✅
(0, 4)✅
(1, 3)❌
(1, 0)❌
(0, 2)✅
(1, 2)❌
(0, 3)✅
(1, 3)❌
(0, 4)❌
(0, 1)❌
(0, 1)❌
(0, 2)❌
(0, 3)❌
(0, 4)❌
(0, 0)❌
태평양 집합: {(0, 0), (1, 0), (0, 1), (1, 1), (2, 1), (3, 1), (2, 2), (1, 2), (1, 3), (1, 4), (0, 4), (0, 2), (0, 3)}그 다음 태평양과 접하는 상단 가장자리리 섬들을 왼쪽부터 오른쪽으로 가로 방향 탐색합니다. 대서양으로 비가 흐를 수 있는 섬을 추가적으로 3개 더 찾을 수 있습니다.
(1, 0)❌
(2, 0)✅
(3, 0)✅
(3, 1)❌
(1, 0)❌
(2, 1)❌
(3, 0)❌
(4, 0)✅
(3, 0)❌
태평양 집합: {(0, 0), (1, 0), (0, 1), (1, 1), (2, 1), (3, 1), (2, 2), (1, 2), (1, 3), (1, 4), (0, 4), (0, 2), (0, 3), (2, 0), (3, 0), (4, 0)}이제 대서양과 접하는 하단 가장자리 섬들을 왼쪽부터 오른쪽으로 가로 방향 탐색합니다. 대서양으로 비가 흐를 수 있는 11개의 섬을 찾았습니다.
(4, 0)✅
(3, 0)✅
(3, 1)✅
(4, 1)✅
(3, 1)❌
(4, 2)✅
(3, 2)✅
(4, 2)❌
(2, 2)✅
(3, 3)✅
(3, 4)✅
(3, 1)❌
(4, 3)✅
(3, 3)❌
(4, 4)✅
(3, 4)❌
(4, 1)❌
(4, 0)❌
(4, 2)❌
(4, 3)❌
(4, 4)❌
대서양 집합: {(4, 0), (3, 0), (3, 1), (4, 1), (4, 2), (3, 2), (2, 2), (3, 3), (3, 4), (4, 3), (4, 4)}그 다음 대서양과 접하는 우측 가장자리 섬들을 위부터 아래로 세로 방향 탐색합니다. 대서양으로 비가 흐를 수 있는 섬을 추가적으로 5개 더 찾을 수 있습니다.
(0, 4)✅
(1, 4)✅
(0, 4)❌
(1, 3)✅
(1, 4)❌
(2, 4)✅
(3, 4)❌
(1, 4)❌
(2, 3)✅
(3, 3)❌
(1, 3)❌
(2, 2)❌
(3, 4)❌
(4, 4)❌
대서양 집합: {(4, 0), (3, 0), (3, 1), (4, 1), (4, 2), (3, 2), (2, 2), (3, 3), (3, 4), (4, 3), (4, 4), (0, 4), (1, 4), (1, 3), (2, 4), (2, 3)}최종적으로 태평양으로 비가 흐를 수 있는 섬의 집합과 대서양으로 비가 흐를 수 있는 섬의 집합의 교집합을 구해보면 총 7개의 섬을 얻을 수 있습니다. 🅿️는 태평양으로 비가 흐를 수 있는 섬을 나타내고, 🅰️는 대서양으로 비가 흐를 수 있는 섬을 나타내며, 🟢은 태평야과 대서양 모두로 비가 흐를 수 있는 섬을 나타냅니다.
🅿️🅿️🅿️🅿️🟢
🅿️🅿️🅿️🟢🟢
🅿️🅿️🟢🅰️🅰️
🟢🟢🅰️🅰️🅰️
🟢🅰️🅰️🅰️🅰️
태평양 집합: {(0, 0), (1, 0), (0, 1), (1, 1), (2, 1), (3, 1), (2, 2), (1, 2), (1, 3), (1, 4), (0, 4), (0, 2), (0, 3), (2, 0), (3, 0), (4, 0)}
대서양 집합: {(4, 0), (3, 0), (3, 1), (4, 1), (4, 2), (3, 2), (2, 2), (3, 3), (3, 4), (4, 3), (4, 4), (0, 4), (1, 4), (1, 3), (2, 4), (2, 3)}
교집합: {(0, 4), (1, 3), (1, 4), (2, 2), (3, 0), (3, 1), (4, 0)}그럼 이 알고리즘을 파이썬으로 구현해볼까요?
class Solution:
def pacificAtlantic(self, heights: List[List[int]]) -> List[List[int]]:
n_rows, n_cols = len(heights), len(heights[0])
pacific, atlantic = set(), set()
def dfs(visited, row, col):
if (row, col) in visited:
return
visited.add((row, col))
for r, c in (
[row + 1, col],
[row - 1, col],
[row, col + 1],
[row, col - 1],
):
if 0 <= r < n_rows and 0 <= c < n_cols:
if heights[row][col] <= heights[r][c]:
dfs(visited, r, c)
for c in range(n_cols):
dfs(pacific, 0, c) # uppermost row
dfs(atlantic, n_rows - 1, c) # lowermost row
for r in range(n_rows):
dfs(pacific, r, 0) # leftmost column
dfs(atlantic, r, n_cols - 1) # rightmost column이 풀이의 복잡도는 O(r * c)로 이전 풀이에 비해 대폭 향상이 됩니다.
최악의 경우로 배열이 모두 같은 값으로 채워져 있다고 하더라도, O(2n)의 시간이 소모될 것이기 때문입니다.
마치면서
이 문제가 너무 어려우셨다면 비슷하지만 좀 더 쉬운 문제인 Number of Islands도 풀어보시라고 추천드립니다. 코딩 테스트에서 그래프 자료구조를 어떻게 다루는지에 대해서 더 공부하고 싶으시다면 관련 게시물을 참고 바랄께요.