32. Number of Islands

🎯 leetcode - 200. Number of Islands

---

📌 문제

- 파이썬 알고리즘 인터뷰 32번 문제
- 섬의 개수 세기

📌 날짜

2020.02.03

📌 시도 횟수

Failed

---

💡 Code

class Solution:
    def numIslands(self, grid: List[List[str]]) -> int:
        def dfs(grid: List[List[str]], i: int, j: int):
            # 더이상 땅이 아닌 경우에 종료
            if i < 0 or i >= len(grid) or j < 0 or j >= len(grid[0]) or grid[i][j] != "1":
                return

            grid[i][j] = "x" # 1이 아닌 다른 문자로 방문한 땅을 마킹
            dfs(grid, i + 1, j)  # 동
            dfs(grid, i - 1, j)  # 서
            dfs(grid, i, j + 1)  # 남
            dfs(grid, i, j - 1)  # 북
        

        # grid = []인 경우 예외 처리
        if not grid:
            return 0
        
        count = 0
        for i in range(len(grid)):
            for j in range(len(grid[0])):
                if grid[i][j] == "1": # 땅인 경우
                    dfs(grid, i, j)   # dfs로 방문한 육지를 모두 마킹
                    count += 1        # 육지 탐색 후 섬의 개수 카운트 1 증가

        return count

💡 문제 해결 방법

1. 차례대로 grid를 각각 순회한다.

2. 육지('1')를 발견하면 네 방향 각각 dfs 재귀를 이용하여 탐색한다.
  2-1) 함수 상단에 육지가 아닌 경우(바다이거나, 범위를 초과했거나) return으로 종료하도록 설정한다.
  2-2) 이미 방문한 육지는 1이 아닌 다른 값("x")으로 마킹한다.
      -> 그래야 다음번에 다시 계산하는 경우가 생기지 않는다.
  2-3) 현재 위치의 동,서,남,북을 모두 dfs 재귀로 탐색한다. 네 방향 모두 return 될때까지...

3. dfs 함수를 빠져나온 후에는 해당 땅과 연결된 모든 땅을 방문한 것이므로, 섬의 개수(count)를 1 증가시킨다.

4. 모두 순회를 마치면 최종적으로 섬의 개수(count)를 반환한다.

💡 새롭게 알게 된 점

🌵 파이썬의 중첨 함수
- 위의 코드에서는 dfs 함수에 grid를 매번 넘기는 번거로움을 해결하기 위해 중첩함수 기능을 활용했다.
- 중첨 함수로 dfs를 구현하면 numIslands() 함수 내에서 선언된 변수를 dfs 안에서도 자유롭게 사용할 수 있다.
- 또한 self. 구문도 제거할 수 있어 코드가 깔끔해진다. 

🌵 그래프와 dfs 재귀
- 본 문제 유형을 그래프형으로 변환해서 풀 수 있음을 알게 되었다.
- 드디어 그래프 파트에 들어갔다. 처음이라서 어렵다😥

---

🍡이해가 잘 안된다면🍡