문제

• 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

결과

개느리네,,,,,ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
근데 solution에 있는 97% 풀이와 알고리즘은 같은데.. solution은 set으로 visited를 만들고, recursion dfs로 풀이 했다

기존 내 풀이에서 bfs를 dfs로 바꾸면 조금 더 빨라진다.