Number of Islands - LeetCode

Problem

1. input: 1과 0으로 채워진 이차 행렬 grid
2. output: 1은 땅을, 0은 바다를 뜻할 때, 서로 다른 섬의 갯수 리턴
3. 연결된 1은 하나의 섬으로 취급
   • m == grid.length
   • n == grid[i].length
   • 1 <= m, n <= 300
   • grid[i][j] is '0' or '1'.

Idea

전체 grid를 탐색하여 1을 찾고, 찾은 1을 시작으로 DFS 탐색하여 연결된 1을 체크해주면 된다.

이때 방문(확인)한 1을 0으로 바꿔주면 별도의 visited 배열 생성 없이 체크 가능

Solution

1. DFS

   grid를 탐색하면 1 찾기

   1 찾으면 count + 1

   찾은 1을 시작으로 DFS로 연결된 1 찾기(1을 0으로 변경하여 체크)

   class Solution {
       fun numIslands(grid: Array<CharArray>): Int {
           var answer = 0
           for (i in grid.indices) {
               for (j in grid[0].indices) {
                   if (grid[i][j] == '1') {
                       answer++ // 섬 개수 + 1
                       dfsSearch(grid, i, j)
                   }
               }
           }
           return answer
       }
   
       private fun dfsSearch(grid: Array<CharArray>, i: Int, j: Int) {
           if (i in grid.indices && j in grid[0].indices && grid[i][j] == '1') {
               grid[i][j] = '0' // 방문한 좌표는 0으로 변경
               dfsSearch(grid, i - 1, j) // 상
               dfsSearch(grid, i + 1, j) // 하
               dfsSearch(grid, i, j - 1) // 좌
               dfsSearch(grid, i, j + 1) // 우
           }
       }
   }
   

   시간 복잡도: 배열 탐색 = n^2

   

Point