[Leetcode 200] Number of Islands

🍎 Number of Islands

문제 링크

💿 문제

   Given an m x n 2D binary grid grid which represents a map of '1's (land) and '0's (water), return the number of islands.

 

⚾ 코드

    def solution(grid):

        W = len(grid[0])
        H = len(grid)

        visited = [[False]*W for _ in range(H)]
        count = 0

        dx = [-1, 1, 0, 0]
        dy = [0, 0, -1, 1]

        def check_range(x, y):
            # print(x, y)
            if x >= 0 and x < H and y >= 0 and y < W:
                # print(True)
                return True
            # print(False)
            return False

        def dfs(x, y):
            for i in range(4):
                nx = x+dx[i]
                ny = y+dy[i]
                # print()
                # print("dfs 함수 안", nx, ny)
                if check_range(nx, ny) and grid[nx][ny] == "1" and visited[nx][ny] == False:
                    visited[nx][ny] = True
                    dfs(nx, ny)

        for i in range(H):
            for j in range(W):
                if grid[i][j] == "1" and visited[i][j] == False:
                    visited[i][j] = True
                    dfs(i, j)
                    count += 1

        return count


print(solution([
    ["1", "1", "0", "0", "0"],
    ["1", "1", "0", "0", "0"],
    ["0", "0", "1", "0", "0"],
    ["0", "0", "0", "1", "1"]
]))

 

🔔 해결과정 & 깨달은 점

• 스택과 재귀함수를 사용해 풀었다.
• x와 y의 범위를 꼭 확인해야 한다!
• 가로와 세로의 길이를 바꿔 써서 오류가 났었다. 바꿔 쓰지 않도록 주의하자.