Graphs: 200. Number of Islands

200. Number of Islands

 

https://youtu.be/pV2kpPD66nE?si=lYen92FEUHgGfFzQ

 

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        # grid가 비어있으면 0을 반환 (예외 처리)
        # If the grid is empty, return 0 (edge case handling)
        if not grid:
            return 0

        # grid의 행(Row) 수와 열(Col) 수를 변수에 저장
        # Store the number of rows (ROWS) and columns (COLS) in variables
        ROWS = len(grid)
        COLS = len(grid[0])

        # 방문한 좌표를 저장하기 위한 집합 (visited)
        # Set to store visited coordinates
        visited = set()

        # 섬의 개수를 저장할 변수 (isIlands)
        # Variable to store the number of islands
        isIlands = 0

        # BFS를 위한 함수 정의
        # Define the BFS function
        def bfs(r, c): 
            # BFS는 재귀가 아니라 큐를 사용
            # BFS uses a queue, not recursion
            from collections import deque  # deque 임포트

            # 현재 좌표를 방문 처리하고 큐에 추가
            # Mark the current coordinate as visited and add it to the queue
            q = deque()
            visited.add((r, c))
            q.append((r, c))

            # 큐가 빌 때까지 반복 (BFS 순회)
            # Iterate while the queue is not empty (BFS traversal)
            while q:
                # 큐에서 좌표를 꺼냄
                # Pop a coordinate from the queue
                rr, cc = q.popleft()

                # 이동 방향을 정의 (상, 하, 좌, 우)
                # Define movement directions (up, down, left, right)
                direction = [1, 0], [-1, 0], [0, 1], [0, -1]
                
                # 모든 방향으로 탐색
                # Explore in all directions
                for dr, dc in direction:
                    R, C = rr + dr, cc + dc

                    # 조건: 새로운 좌표가 grid 범위 내에 있고,
                    # 값이 "1"이며, 방문하지 않았을 경우
                    # Condition: The new coordinate is within the grid bounds,
                    # has value "1", and has not been visited
                    if (R in range(ROWS) and 
                        C in range(COLS) and
                        grid[R][C] == "1" and
                        (R, C) not in visited):
                        
                        # 큐에 추가하고 방문 처리
                        # Add to queue and mark as visited
                        q.append((R, C))
                        visited.add((R, C))

        # grid의 모든 좌표를 탐색
        # Traverse through all coordinates in the grid
        for r in range(ROWS):
            for c in range(COLS):
                # 값이 "1"이고 아직 방문하지 않은 좌표라면
                # If the value is "1" and the coordinate has not been visited
                if grid[r][c] == "1" and (r, c) not in visited:
                    # BFS 실행 (연결된 모든 육지 탐색)
                    # Run BFS (explore all connected lands)
                    bfs(r, c)

                    # 새로운 섬 발견 시 섬 개수 증가
                    # Increment the island count upon discovering a new island
                    isIlands += 1

        # 총 섬의 개수를 반환
        # Return the total number of islands
        return isIlands

 

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        # 섬개수
        # 4방향 검색
        # '1' 이 섬, '0'이 물

        if not grid:
            return 0

        ROWS, COLS = len(grid), len(grid[0])

        visit = set()
        isLands = 0

        directions = [[1, 0], [0, 1], [-1, 0], [0, -1]]

        def bfs(r, c):
            visit.add((r, c))
            q = deque()
            q.append((r, c))

            while q:
                r, c = q.popleft()
                for dr, dc in directions:
                    R, C = r+dr, c+dc

                    if R in range(ROWS) and C in range(COLS) and grid[R][C] == "1" and (R, C) not in visit:
                        visit.add((R, C))
                        q.append((R, C))


        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c] == "1" and (r, c) not in visit: 
                    bfs(r, c)
                    isLands += 1

        return isLands

 

최종 코드: dfs, visit 사용

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        direction = [[1, 0], [-1, 0], [0, 1], [0, -1]]

        if not grid:
            return 0

        ROWS, COLS = len(grid), len(grid[0])
        visit = set() # 방문처리
        

        def dfs(r, c):
            # 행렬 범위에 있지 않거나, 물이거나, 이미 방문했으면
            if (r<0 or c<0 or r>=ROWS or c>=COLS or grid[r][c]=='0' or (r, c) in visit):
                return
            
            # 행렬 범위에 있고, 육지이면서, 방문 안했으면
            visit.add((r, c))  # 방문 처리

            # 4방향 탐색
            for dr, dc in direction:
                nr, nc = dr+r, dc+c
                dfs(nr, nc)
            

        island = 0
        for r in range(ROWS):
            for c in range(COLS):
                if grid[r][c] == '1' and (r, c) not in visit:
                    dfs(r, c)
                    island +=1
        return island