LeetCode[417] - Pacific Atlantic Water Flow

문제

LeetCode 417 : Pacific Atlantic Water Flow

풀이

일반적으로 모든 점에 대해서 DFS / BFS를 통해서 전체 탐색하는 방법이 있을 것이다. 그러나 위와 같은 방법에서는 시간복잡도를 줄이고자 다른 방법으로 접근하였다.

1. Pacific Ocean과 맞닿아 있는 지역들을 DFS 시작 점으로 잡는다.
2. 각 지역에서 현재 위치한 지역보다 높이가 같거나 높은 지역을 기준으로 DFS를 실행한다.
3. DFS를 완료한 후에 전부 visited 배열을 표시하면, Pacific Ocean에 도달할 수 있는 지역들이 표시된다.
4. 같은 방법으로 Atlantic Ocean에 도달할 수 있는 지역을 구한다.
5. 두 지역에 모두 도달할 수 있는 겹치는 지역을 구해서 출력한다.

코드

def search(heights):
    col = len(heights)
    row = len(heights[0])

    result = []

    pacific_visited = [[0] * row for _ in range(col)]
    atlantic_visited = [[0] * row for _ in range(col)]

    pacific_stack = []
    atlantic_stack = []

    for i in range(col):
        pacific_stack.append([i, 0])
        pacific_visited[i][0] = 1

    for i in range(1, (row)):
        pacific_stack.append([0, i])
        pacific_visited[0][i] = 1

    for i in range(col):
        atlantic_stack.append([i, row - 1])
        atlantic_visited[i][row - 1] = 1

    for i in range(0, (row - 1)):
        atlantic_stack.append([col - 1, i])
        atlantic_visited[col - 1][i] = 1

    d_row = [0, 0, 1, -1]
    d_col = [1, -1, 0, 0]
    
    
    while (pacific_stack):
        node = pacific_stack.pop()
        node_col = node[0]
        node_row = node[1]
        node_height = heights[node_col][node_row]

        pacific_visited[node_col][node_row] = 1
        for i in range(4):
            n_row = node_row + d_row[i]
            n_col = node_col + d_col[i]

            if (n_row >= 0 and n_col >= 0 and n_row < row and n_col < col):
                if (pacific_visited[n_col][n_row] == 0 and heights[n_col][n_row] >= node_height):
                    pacific_stack.append([n_col, n_row])

    while (atlantic_stack):
        node = atlantic_stack.pop()
        node_col = node[0]
        node_row = node[1]
        node_height = heights[node_col][node_row]

        atlantic_visited[node_col][node_row] = 1
        for i in range(4):
            n_row = node_row + d_row[i]
            n_col = node_col + d_col[i]

            if (n_row >= 0 and n_col >= 0 and n_row < row and n_col < col):
                if (atlantic_visited[n_col][n_row] == 0 and heights[n_col][n_row] >= node_height):
                    atlantic_stack.append([n_col, n_row])

    for i in range(col):
        for j in range(row):
            if (pacific_visited[i][j] == 1 and atlantic_visited[i][j] == 1):
                result.append([i, j])

    return result