[파이썬 알고리즘 인터뷰][그래프] 섬의 개수

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

1로 이어진 섬의 개수 출력

 

책에서 구현된 코드

def numIslands(self, grid: list[list[str]]) -> int:
    def dfs(i, j):
        if i < 0 or i >= len(grid) or \
        j < 0 or j >= len(grid[0]) or \
        grid[i][j] != '1':
            return
        
        grid[i][j] = 0
        
        dfs(i+1, j)
        dfs(i-1, j)
        dfs(i, j+1)
        dfs(i, j-1)
        
    count = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            if grid[i][j] == '1':
                dfs(i, j)
                count += 1
                
    return count

 

기억해야할 기법

• grid에서 범위를 나타내는 함수 (in_range)에서 아래와 같은 표현이 가능
  
  • -1 < x < n and -1 < y < m
• discovered(2차원 리스트)를 만들 시 주의사항
  • 아래와 같은 방식으로 사용하면 안됨
    [[True] * m] * n
  • shallow list라고 함, 아마 immutable 객체인 bool에 대해 address만 저장하는 리스트가 copy 과정에서 address가 copy되면서, address 값이 바뀌면서 모든 열의 값이 다같이 바뀌는듯
  • 나중에 더 확실히 알아보자
  • 아래과 같이 사용하자
    [[True for _ in range(m)] for _ in range(n)]

https://stackoverflow.com/questions/2397141/how-to-initialize-a-two-dimensional-array-in-python/44382900#comment112946130_44382900

How to initialize a two-dimensional array in Python?

https://www.geeksforgeeks.org/python-using-2d-arrays-lists-the-right-way/

Python | Using 2D arrays/lists the right way - GeeksforGeeks

 

내가 구현한 코드

def numIslands(grid: list[list[str]]) -> int:
    n, m = len(grid), len(grid[0])
    discovered = [[True for _ in range(m)] for _ in range(n)]
    direction = [(0,1),(1,0),(-1,0),(0,-1)]
    answer = 0

    def in_range(x: int, y: int):
        return -1 < x < n and -1 < y < m

    def dfs(i: int, j: int) -> bool:
        if in_range(i, j) and discovered[i][j]:
            if grid[i][j] == "1":
                discovered[i][j] = False
                for d in direction:
                    dfs(i+d[0], j+d[1])
                return True
        return False

    for i in range(n):
        for j in range(m):
            if dfs(i, j):
                answer += 1

    return answer

• 책에서 구현한 알고리즘과 내가 구현한 알고리즘이 얼핏 비슷해보이는데, 속도가 10ms 정도 차이남
  • 이 문제에서는 discovered가 필요 없음
    - discovered를 없애도 비슷함
  • 책에서 구현한 알고리즘
    - i / j의 loop에서 grid가 "1"이면 dfs 실행
  • 내가 구현한 알고리즘
    - dfs를 호출하고 내부에서 판단
    - 따라서, dfs의 recursive중 depth가 1인 부분이 i / j의 range를 보장 받음에도 불구하고, 모두 in_range로 인해 범위를 검사함