[ LeetCode - 200 ] Number of Islands

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

Number of Islands - LeetCode

와 대박... 그래프 문제 진짜 오랜만에 푸는데 알고리즘을 오랜만에 해서 그런가 기본 그래프 문제인데도 새롭게 했다.

 

0과 1로 이루어진 그래프 내에서 1이 이어진 땅이 몇 개 있는지 찾는 문제다.

어떤 로직도 상관 없지만 dfs 알고리즘을 사용 하였고, visited 체크는 하지 않고, 방문한 노드를 '1'에서 '0'으로 변경 하였다.

 

[ 📌 풀이 ]

1. 그리드 좌표중에 '1'인 좌표를 선택해서 dfs 알고리즘 수행
2. dfs 알고리즘 수행중에는 방문한 노드는 '0'으로 변경해서 방문처리
3. dfs 알고리즘이 처음으로 수행되는 시점에 ans에 +1 해서 정답 누적

 

[ 📌 함수 ]

• numIsIands: grid를 순회하며 '1'인 좌표를 찾아내서 dfs 호출하는 함수
• dsf: dsf 알고리즘 수행 함수로 방문은 현 좌표 기준으로 상, 하, 좌, 우 방문하고, 방문한 좌표는 '0'으로 변경해서 방문 처리 한다.
• isValid: 방문하는 좌표가 유효한 좌표인지 체크하는 함수

 

[ 📌 코드 - Python ]

class Solution:
    move = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    rows = None
    cols = None

    def numIslands(self, grid: list[list[str]]) -> int:
        self.rows, self.cols = len(grid), len(grid[0])
        ans = 0

        for x in range(self.rows):
            for y in range(self.cols):
                if grid[x][y] == "1":
                    ans += 1
                    self.dfs(grid, x, y)
        
        return ans

    def dfs(self, grid: list[list[str]], x: int, y: int) -> None:
        if grid[x][y] == "0":
            return
        
        grid[x][y] = "0"
        
        for moveX, moveY in self.move:
            newX = moveX + x
            newY = moveY + y

            if self.isValid(newX, newY) and grid[newX][newY] == "1":
                self.dfs(grid, newX, newY)

    def isValid(self, x, y) -> bool:
        return 0 <= x < self.rows and 0 <= y < self.cols 

s = Solution()
result = s.numIslands([
  ["1","1","0","0","0"],
  ["1","1","0","0","0"],
  ["0","0","1","0","0"],
  ["0","0","0","1","1"]
])

print(result)