[그래프] 섬의 개수

200 | Number of Islands
https://leetcode.com/problems/number-of-islands/

 

 

 

작성 코드

 

• 접근 방법을 모르겠음

 

이상 코드

 

중첩 함수 이용

 

class Solution:
    def numIslands(self, 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':
                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)
                    # 모든 육지 탐색 후 카운트 1 증가
                    count += 1
        return count

 

• 동서남북이 모두 연결된 그래프로 가정
• 방문한 경로를 별도로 저장해주지 않고, 0 값으로 지정 (중복하여 count하지 않도록)

 

• 동서남북 탐색 -> 동, 남만 탐색하면 안 되는 것인가?

 

• 동그라미 1을 탐색할 때, 좌우를 탐색해야 함
• 동, 남 방향으로만 탐색하면 3행 1열의 1을 놓쳤을 것