Leetcode 200. Number of Islands

요즘에는 개발자들이 회사에 취업하기 위해서 사용한다는 리트코드 (leetcode) 사이트의 문제들을 풀어보고 있습니다. 이제 막 시작한 초보자라 힘든 점이 많아서 이렇게 글로 남겨서 복습하려고 합니다.

 

문제: Number of Islands
등급: Medium

내용:

'1'(땅)과 '0'(물)의 지도를 나타내는 m x n 2D 이진 grid가 주어지면 섬의 수를 반환합니다.

섬 (1로 형성)은 물(0)로 둘러싸여 있으며 인접한 토지를 수평 또는 수직으로 연결하여 형성됩니다. grid의 네 모서리는 모두 물로 둘러싸여 있다고 가정할 수 있습니다.

 

<코드>

도저히 안 풀려서 discussion보고 거의 베낀 푼 코드

class Solution(object):
    def numIslands(self, grid):
        if not grid:
            return 0
        
        count = 0
        # row
        for i in range(len(grid)):
            # column
            for j in range(len(grid[0])):
                if grid[i][j] == '1':
                    self.dfs(grid,i,j)
                    # since 1s are turned into #s, the count would only increase by one per island
                    count += 1
                    
        return count
    
    # turn 1s into #s 
    def dfs(self, grid, i, j):
        # 1st. check if it is out of bound or check if it is not 1
        if i < 0 or j < 0 or i>= len(grid) or j >= len(grid[0]) or grid[i][j] != '1':
            return
        # turn that one into #
        grid[i][j] = '#'
        # do NESW transitions
        self.dfs(grid, i+1, j)
        self.dfs(grid, i, j+1)
        self.dfs(grid, i-1, j)
        self.dfs(grid, i, j-1)

<논리>

우선 간단하게, grid가 비어있으면 0을 반환한다. 

 

그리고는, grid의 숫자 하나씩 하나씩 for loop을 통해 살펴본다. 여기서 숫자가 == '1'이면 dfs 함수를 사용한다.

 

dfs 함수는 1을 #로 바꿔준다. 굳이 #일 필요는 없지만 1 또는 0 이면 안된다. 이 dfs 함수에서는 그 숫자를 나타내는 인덱스 i와 j가 grid의 바깥에 있는지, 숫자가 1이 아닌지를 확인한다. 바깥에 있거나 1이 아니라면 아무것도 반환하지 않는다. 

 

하지만 if statement를 통과하면 동서남북 하나씩 다 dfs 함수를 또 하게함으로써 주위를 살펴보게 된다. 이렇게 "섬"의 모든 1은 "#"으로 바뀌게 된다.

 

다시 위의 for loop으로 돌아가서 grid[i][j]가 1 인지 확인한다. 이미 한 섬은 count가 되었고 #가 되었기 때문에 이 for loop은 안전하게 모든 숫자를 살펴보며 섬의 개수를 확인할 수 있다.

 

<오류, 힘들었던 점>

이런 아이디어, 이런 생각은 어떻게 하는 것입니까.

 

<총평>

 

Happy coding!