[LeetCode] 200. Number of Islands - Python

[LeetCode] 200. Number of Islands - Python

 

Number of Islands - LeetCode

 

문제

1을 육지로, 0을 물로 가정한 2D 그리드 맵이 주어졌을 때, 섬의 개수를 계산하세요.

즉 연결되어있는 1의 덩어리 수를 구하는 문제입니다.

 

 

아이디어

DFS 그래프 탐색을 이용해서 해결하는 대표적인 문제이다. 다음과 같은 알고리즘으로 코드를 작성하여 문제를 해결했다.

1) 각 위치(i, j)를 순서대로 탐색하면서 땅(1)인지 확인하고, 동서남북으로 이동하면서 땅이 아니라면 함수를 종료한다.

함수가 종료되면 섬 1개를 찾았다는 의미로 count +=1를 진행한다.

2) 동서남북으로 이동하며 탐색하는 과정을 구현하기 위해 재귀함수를 사용한다.

3) 탐색 과정에서 한번 확인한 땅은 0으로 설정해준다. 그래야 같은 지역을 재탐색하여 중복되는 경우를 막아준다.

 

 

코드

def numIslands(grid: list[list[str]]) -> int:
    def dfs(i, j):
        #땅이 아니라면 함수를 끝내기
        if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] != '1':  #grid[i][j] == '0'은 오류
            return

        #땅이든 아니든 탐색했으면 0으로 설정
        grid[i][j] = 0

        #땅이라면, 상하좌우 탐색
        dfs(i+1, j)
        dfs(i-1, j)
        dfs(i, j-1)
        dfs(i, j+1)

    #본 탐색 시작
    count = 0
    for i in range(len(grid)):
        for j in range(len(grid[0])):
            #땅을 찾으면 함수 시작
            if grid[i][j] == '1':
                dfs(i, j)

                #한번 끝나면 지나온 길은 0으로 바꾸므로 중복되지 않음, 따라서 함수가 끝나면 바로 1을 더해줘도 ok
                count += 1

    return count