[leetcode] 200. Number of Islands 파이썬 코드

1은 land이고, 0은 water를 나타내는데 인접한 땅(1)은 하나의 섬이라고 생각할 때 섬의 개수가 총 몇 개인지 세는 문제이다.

이 문제는 읽자마자 flood fill 알고리즘을 써야겠다는 생각이 들었다. 

 

큐에 시작 정점을 넣어주고 방문 처리 한 다음에 사방 (four directions)을 탐색한다. 

범위에도 포함되면서 (IndexError: list index out of range 를 내면 안 되니까 범위를 체크해줘야 한다) "1"이고 한 번도 방문한 적이 없다면, 큐에 넣어주고 방문처리 해준다.

 

class Solution(object):
    def range_check(self, row, col):
        if 0 <= row and row < m and 0 <= col and col < n:
            return True
        return False

    def floodfill(self, grid, visited, row, col):
        q = [] # 시작 큐 first in, first out
        q.append([row, col]) # 큐에 넣기 
        visited[row][col] = True # 방문처리 
        dr = [1, 0, -1, 0]
        dc = [0, 1, 0, -1]

        while q:
            cr, cc = q.pop(0) # current row, current col
            for dir in range(4):
                nr = cr + dr[dir]
                nc = cc + dc[dir]
                if range_check(nr, nc) and grid[nr][nc] == "1" and visited[nr][nc] == False:
                    q.append([nr, nc])
                    visited[nr][nc] = True

        return grid, visited

    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        m = len(grid) # number of row
        n = len(grid[0]) # number of col
        visited = [[False for i in range(n)] for i in range(m)]

        num_island = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == "1" and visited[i][j] == False:
                    grid, visited = floodfill(grid, visited, i, j)
                    num_island += 1

        return num_island

 

이렇게 하면 Runtime Error가 뜬다.

 

- 클래스 내부에서 메서드를 호출할 때는 self를 통해 접근해야 한다.

 

grid, visited = floodfill(grid, visited, i, j) → grid, visited = self.floodfill(grid, visited, i, j)

if range_check(nr, nc) and grid[nr][nc] == "1" and visited[nr][nc] == False: →  if self.range_check(nr, nc) and grid[nr][nc] == "1" and visited[nr][nc] == False: 

 

- m과 n 변수가 numIslands라는 함수 안에서 정의되어 있기 때문에 m과 n 변수도 range_check과 floodfill 함수의 파라미터로 넣어줘야 한다. 

 

이 2가지를 반영해서 코드를 수정했다.

 

class Solution(object):
    def range_check(self, row, col, m, n):
        if 0 <= row and row < m and 0 <= col and col < n:
            return True
        return False

    def floodfill(self, grid, visited, row, col, m, n):
        q = [] # 시작 큐 first in, first out
        q.append([row, col]) # 큐에 넣기 
        visited[row][col] = True # 방문처리 
        dr = [1, 0, -1, 0]
        dc = [0, 1, 0, -1]

        while q:
            cr, cc = q.pop(0) # current row, current col
            for dir in range(4):
                nr = cr + dr[dir]
                nc = cc + dc[dir]
                if self.range_check(nr, nc, m, n) and grid[nr][nc] == "1" and visited[nr][nc] == False:
                    q.append([nr, nc])
                    visited[nr][nc] = True

        return grid, visited

    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        m = len(grid) # number of row
        n = len(grid[0]) # number of col
        visited = [[False for i in range(n)] for i in range(m)]

        num_island = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == "1" and visited[i][j] == False:
                    grid, visited = self.floodfill(grid, visited, i, j, m, n)
                    num_island += 1

        return num_island

 

 

리팩토링

그런데 나는 지금 list로 큐를 만들고, pop(0) 이렇게 했다. 

이것은 O(n) 의 시간 복잡도를 가져서 비효율적이다. 

왜냐하면 맨 앞의 Element를 빼내면, 뒤에 있는 Elements가 앞으로 한 칸씩 와야되기 때문이다.

 

그래서 deque을 사용했다.

 

from collections import deque

class Solution(object):
    def range_check(self, row, col, m, n):
        if 0 <= row and row < m and 0 <= col and col < n:
            return True
        return False

    def floodfill(self, grid, visited, row, col, m, n):
        q = deque() # 시작 큐 first in, first out
        q.append([row, col]) # 큐에 넣기 
        visited[row][col] = True # 방문처리 
        dr = [1, 0, -1, 0]
        dc = [0, 1, 0, -1]

        while q:
            cr, cc = q.popleft() # current row, current col
            for dir in range(4):
                nr = cr + dr[dir]
                nc = cc + dc[dir]
                if self.range_check(nr, nc, m, n) and grid[nr][nc] == "1" and visited[nr][nc] == False:
                    q.append([nr, nc])
                    visited[nr][nc] = True

        return grid, visited

    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        m = len(grid) # number of row
        n = len(grid[0]) # number of col
        visited = [[False for i in range(n)] for i in range(m)]

        num_island = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == "1" and visited[i][j] == False:
                    grid, visited = self.floodfill(grid, visited, i, j, m, n)
                    num_island += 1

        return num_island

 

 

어라..? 더 빠르지는 않았다.

 

리스트 대신 튜플

여기서 더 나아가서 내가 좌표를 넣을 때 리스트를 사용했는데 튜플을 사용해서 다시 돌려봤다.

리스트는 mutable 자료형이고 튜플은 immutable 자료형이어서 전자는 한 번 생성된 후에도 내부의 element 값을 변경할 수 있지만 후자는 값을 바꿀 수 없다.

좌표값을 바꿀 일은 없으므로 여기서는 튜플도 적절하다. 

 

q.append([row, col]) → q.append((row, col))

 

그런데 튜플이 리스트보다 time, memory 관점에서 more efficient하다. [참고]

 

 

 

리스트를 썼을 때보다 튜플을 썼을 때 runtime이 256ms → 233ms로 줄었다.