https://leetcode.com/problems/number-of-islands/

내 intial idea는 일단 recursion (either DFS or BFS)로 풀어야한다는 것과, if 주변이 wall, 혹은 내가 visited 혹은 0인 경우에는 number of islands += 1 해주어야한다는 것이었다.
DFS 혹은 BFS를 할 경우 helper function을 만들어주어야한다는 것까지 생각해냈다. 문제에서 주어진 numIslands 함수의 경우 오직 grid만 parameter로 넘길 수 있기 때문이다. DFS, BFS 를 사용할 경우 helper function을 만들어 내가 체크해야할 인덱스를 넘겨주어야한다고 생각했다.

하지만 두루뭉술하게 아이디어를 떠올릴 수만 있었고, 실제 코드 구현은 하지 못했다.

Approach 1. DFS

class Solution:
    def dfs(self, grid, i, j):
        # 내가 0 혹은 visited 거나 주변이 다 wall일때
        if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] != '1':
            return
        
        # 내가 1일때
        grid[i][j] = '#'
        self.dfs(grid, i+1, j)
        self.dfs(grid, i, j+1)
        self.dfs(grid, i-1, j)
        self.dfs(grid, i, j-1)
        
    def numIslands(self, grid: List[List[str]]) -> int:
        if not grid:
            return 0
        
        count = 0 
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    self.dfs(grid, i, j)
                    count += 1
        return count

첫번째 방법은 DFS로 푸는 것이다.
함수 dfs라는 helper function을 만들어 내가 체크해줄 index를 넘겨준다.

만약 내가 현재 확인하는 index, grid[i][j]가 0이거나, '#' (visited)이거나, 혹은 주변이 다 wall (grid의 바깥)인 경우 (base case), 바로 리턴을 해주어 number of islands의 count를 높여준다.

그렇지 않은 경우, 즉 grid[i][j]가 1인 경우, 내 상하좌우를 체크한다. base case에 다다를때까지 함수는 계속 recursively 불리기 때문에 DFS이다.

Approach 2. BFS

from collections import deque
class Solution:
    def numIslands(self, grid):
        count = 0
        queue = deque([])
        
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    grid[i][j] = '#'
                    queue.append((i,j))
                    self.bfs(grid,queue)
                    
                    count += 1
        return count
    
    
    def bfs(self,grid,queue):
        m = len(grid)
        n = len(grid[0])
        
        while queue:
            I,J = queue.popleft()
            # 상하좌우 체크
            for i,j in [I-1,J],[I+1,J],[I,J-1],[I,J+1]:
                if 0<= i < m and 0 <= j < n and grid[i][j] == '1':
                # 만약 boundary 안에 있고 '1'이면 queue에 append
                    queue.append((i,j))
                    grid[i][j] = '#'
                    print(grid)

생각해볼 포인트

왜 이 문제에서 BFS가 DFS보다 빠를까?

깊이가 아주 깊지 않은 경우 상하좌우를 먼저 확인하는 BFS가 더 빠르다.

BFS should typically be faster if the searched element is typically higher up in the search tree because it goes level by level. DFS might be faster if the searched element is typically relatively deep and finding one of many is sufficient.

from: https://stackoverflow.com/questions/47222855/in-what-sense-is-dfs-faster-than-bfs