2022.07.06.md

BFS by queue process (island & water problem)

1. deque 생성, visited set 생성

2. for 로 grid 돌면서 1 and visited == False인 경우에 BFS 시작

3. 처음 시작한 곳이 root node가 되고 visited = True 하고 상하좌우로(조건문으로 경계에 있는 경우는 또 제외해야함) 인접한 노드가 연결된 노드가 됨

4. if 연결된 노드의 1 and visited == False인 경우에 enqueue , visited = True

5. enqueue 가 끝난 후 탐색했던 노드 dequeue

6. queue empty될 때까지 3~5 반복

7. 1. edge case: 1이 하나만 달랑 있을 때 - 루트노드만 enqueue 하고 dequeue하고 끝남

2. 0밖에 없을 때 - 모두 0 and visited == True가 된 후 (BFS 안함) 끝남, result = 0

3. 1밖에 없을 때 - 처음부터 BFS시작, 모든 노드 BFS 이후 끝남

My Code:

    class Solution(object):
    def numIslands(self, grid):
        """
        :type grid: List[List[str]]
        :rtype: int
        """
        from collections import deque
        
        visited = set()
        myq = deque()
        result = 0
        
        for i in range(len(grid)):
            for j in range(len(grid[i])):
                if i*301 + j not in visited and grid[i][j] == '1':
                    # BFS starts from here
                    
                    result += 1
                    
                    myq.append([i, j])
                    visited.add(i*301 + j)
                    
                    while len(myq) != 0:
                        current = myq.popleft()
                    
                        if current[0] > 0 and (current[0]-1)*301 + current[1] not in visited:
                            if grid[current[0]-1][current[1]] == '1':
                                myq.append([current[0]-1, current[1]])
                            visited.add((current[0]-1)*301 + current[1])
                        if current[0] < len(grid)-1 and (current[0]+1)*301 + current[1] not in visited:
                            if grid[current[0]+1][current[1]] == '1':
                                myq.append([current[0]+1, current[1]])
                            visited.add((current[0]+1)*301 + current[1])
                        if current[1] > 0 and current[0]*301 + current[1]-1 not in visited:
                            if grid[current[0]][current[1]-1] == '1':
                                myq.append([current[0], current[1]-1])
                            visited.add(current[0]*301 + current[1]-1)
                        if current[1] < len(grid[i])-1 and current[0]*301 + current[1]+1 not in visited:
                            if grid[current[0]][current[1]+1] == '1':
                                myq.append([current[0], current[1]+1])
                            visited.add(current[0]*301 + current[1]+1)
                            
                        # BFS ends here
                        
                elif i*301 + j not in visited:
                    visited.add(i*301 + j)
                    
        return result

너무 쓸데없는 부분이 많은 느낌이 있지만..(중첩if 4개를 써야만 했나? 싶다. 그럼에도 runtime 상위 24%정도긴 하다..) visited 라는 set에 list를 추가할 수 없다는 걸 알게 되자 m,n <= 300 임을 이용해서 i * 300 + j 를 add한 건 나름 괜찮은 수학적인 아이디어였던 것 같다.

오... 다른 사람 코드를 보니까 따로 visited 판별 집합 같은 걸 만들지 않고 대신 grid의 값을 0으로 넣는 방식을 사용했다. 어차피 0일 때 스킵하는 식의 조건문이니까 충분히 일리가 있는 방식이다(적어도 이 문제에서는).