[LeetCode] 200번 Number of Islands 문제 풀이 (파이썬)

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

Number of Islands - LeetCode

from collections import deque

class Solution:
    # grid, m, n은 bfs함수와 numIslands함수에서 모두 참조할 수 있도록 클래스 변수로 선언
    grid: [[str]]
    m: int
    n: int
        
    def bfs(self, start_i, start_j): # self를 빼먹으면 오류나니 주의
        queue = deque([(start_i, start_j)])
        """
        이 부분에 새 매개변수명을 주지 않고 i, j로 하면 밑에서 오류 나니 조심
        오류 나는 이유는 while문에서 무한루프가 발생하기 때문
        """
        
        while queue: # 큐에 요소가 남아있으면(즉 아직 미탐색의 연결된 "1"(섬)이 남아있다면)
            i, j = queue.popleft() # 아직 미탐색인 큐의 첫 번째 요소
            self.grid[i][j] = "0" # 탐색을 시작하며, 이미 방문한 노드라는 의미로 "0"으로 바꿈
            if (i - 1) >= 0 and self.grid[i - 1][j] == "1" and (i - 1, j) not in queue:
                queue.append((i - 1, j))
            # elif 쓰면 오류남. 말 그대로 "else" if인 상황 아니면 if를 쓰는 게 맞다.
            # 또한 i에서 m이고 j에서 n인 이유는 i가 행을, j가 열을 나타내기 때문. 헷갈리지 말것
            if (i + 1) < self.m and self.grid[i + 1][j] == "1" and (i + 1, j) not in queue:
                queue.append((i + 1, j))
            if (j - 1) >= 0 and self.grid[i][j - 1] == "1" and (i, j - 1) not in queue:
                queue.append((i, j - 1))
            if (j + 1) < self.n and self.grid[i][j + 1] == "1" and (i, j + 1) not in queue:
                queue.append((i, j + 1))
    
    def numIslands(self, grid: List[List[str]]) -> int:
        self.grid = grid # grid를 self.grid에 할당해줌
        self.m = len(grid)
        self.n = len(grid[0])
        
        num_islands = 0
        for i in range(self.m): # 모든 행
            for j in range(self.n): # 모든 열, 즉 각 행, 열의 모든 요소들에 대하여
                if self.grid[i][j] == "1": # 해당 요소의 값이 "1"이면
                    num_islands += 1 # 이는 섬이기 때문에 섬의 개수를 카운트해준다.
                    self.bfs(i, j)
                    # 그리고 해당 섬에 연결된 "1"들(섬의 일부)을 전부 탐색해서 하나의 섬으로 인식하고 넘어간다.
                # 요소의 값이 "0" 즉 섬이 아닌 경우(혹은 bfs에서 이미 탐색한 경우)에는 그냥 넘어가주면 된다.
        
        return num_islands # 섬의 개수 반환

왜 bfs인지 이해를 못했던 문제였는데, 한 줄 한 줄 보다보니 이해가 갔다. 알고리즘 초보의 슬픔...

일단 "1"을 찾으면 이는 섬이기 때문에 카운트를 해준다. 그리고 해당 "1"에 연결된 "1"들 역시 같은 섬이기 때문에, 연결된 모든 "1"들을 한 번씩 탐색해줘야 하는 것. 탐색한 후에는 다시 섬으로 세주면 안되기 때문에 노드의 값을 "0"으로 바꿔서 이중 for 루프에서 탐색하지 않고 무시하도록 한다.

 

같은 아이디어로 dfs로도 풀 수 있다.

class Solution:
    grid: [[str]]
    m: int
    n: int
        
    def dfs(self, i, j):
        # 범위를 벗어나거나 "0"인 노드에 대해서는 건너뜀
        if i < 0 or i >= self.m or j < 0 or j >= self.n or self.grid[i][j] == "0":
            return # 이 부분이 없으면 무한재귀를 하게 되므로 주의할것
        
        self.grid[i][j] = "0" # 방문한 노드에 표시
        self.dfs(i - 1, j)
        self.dfs(i + 1, j)
        self.dfs(i, j - 1)
        self.dfs(i, j + 1)
            
    def numIslands(self, grid: List[List[str]]) -> int:
        self.grid = grid
        self.m, self.n = len(self.grid), len(self.grid[0])
        num_islands = 0
        for i in range(self.m):
            for j in range(self.n):
                if self.grid[i][j] == "1":
                    num_islands += 1
                    self.dfs(i, j)
        return num_islands

 

참고 코드: https://hyoeun-log.tistory.com/121

[파이썬 알고리즘] 12장 - 섬의 개수 (leetcode 200)