[leetcode] 417. Pacific Atlantic Water Flow 파이썬 코드

내가 좋아하는 그래프 문제.

 

왼쪽 위에는 태평양이 있고, 오른쪽 아래에는 대서양이 있다.

이 둘을 건널 수 있는 좌표값들을 리스트에 반환하는 문제다. 

태평양과 대서양을 건널 수 있는 좌표는 그 주변에 있는 섬들의 해수면 높이(sea level)보다 크거나 같아야 한다.

즉, 이웃하는 셀들의 해수면 높이가 내가 위치한 셀의 해수면 높이보다 작거나 같아야 한다. 

 

어떻게 해서 꾸역꾸역 푼 나의 코드는 다음과 같다. 

class Solution(object):
    def isPacific(self, r, c):
        if r == 0 and c == 0:
            return True
        elif r == 0 or c == 0:
            return True
        else:
            return False

    def isAtlantic(self, m, n, r, c):
        if r == m-1 and c == n-1:
            return True
        elif r == m-1 or c == n-1:
            return True
        else:
            return False

    def isFlowing(self, array, r, c):
        m, n = len(array), len(array[0])
        visited = [[False] * n for _ in range(m)]
        pacific_flag = False
        atlantic_flag = False

        # 4 direction search
        dr = [-1, 0, 1, 0]
        dc = [0, -1, 0, 1]

        queue = [[r, c]]
        visited[r][c] = True
        if self.isPacific(r, c): pacific_flag = True
        if self.isAtlantic(m, n, r, c): atlantic_flag = True
        while queue:
            cr, cc = queue.pop(0) # current row, current col
            for i in range(4):
                nr, nc = cr + dr[i], cc + dc[i] # next row, next col
                isInRange = (0 <= nr < m) and (0 <= nc < n)

                # 범위에도 들어가면서, height이 less than or equal to 하면서, 방문한 적이 없다면
                # queue에 넣어주기
                if isInRange and array[cr][cc] >= array[nr][nc] and not visited[nr][nc]:
                    queue.append([nr, nc])
                    visited[nr][nc] = True # 방문처리
                    if self.isPacific(nr, nc): pacific_flag = True
                    if self.isAtlantic(m, n, nr, nc): atlantic_flag = True

        # at the end
        if pacific_flag and atlantic_flag:
            return True

        return False

    def pacificAtlantic(self, heights):
        result = []
        m, n = len(heights), len(heights[0])
        for i in range(m):
            for j in range(n):
                if self.isFlowing(heights, i, j):
                    result.append([i, j])

        return result

 

그런데 너무 오래 걸렸다.

 

 

조금 더 효율적으로 풀 수 있는 방법을 고민해보자.