[LeetCode] Number of Islands

https://leetcode.com/problems/number-of-islands/

 

문제 파악

-2차원 배열이 주어지고, 1이 상하좌우로 있는지 체크하여 섬이 총 몇 개 있는지 센다. (분기체크)

• m == grid.length
• n == grid[i].length
• 1 <= m, n <= 300
• grid[i][j] is '0' or '1'.

접근 방법

-0은 물, 1은 섬. 물 만나거나 범위 벗어나지 않는 이상, 섬 한 덩어리로 본다.

-1이면 계속 순회하며 visit 체크(무한 루프 방지)

-처음 기준 노드는 ‘1’ 나오면 시작. 타고 가서 상하좌우 dfs 체크

⇒ 막히면 return되고, 다른 방향으로 탐색 시작

-If 0이거나, 벽이면 순회 끝(base case)

코드 구현

import java.util.*;
class Solution {
    public int numIslands(char[][] grid) {
        int cnt=0;

        for(int i=0;i<grid.length;i++){
            for(int j=0;j<grid[0].length;j++){
                if(grid[i][j]=='1'){
                    cnt++;
                    dfs(grid,i,j);//1만나면 기준노드 시작
                }
            }
        }
        return cnt;
    }
    public void dfs(char[][] grid,int i,int j){//방향
        if(i>=grid.length || j>=grid[0].length || i<0 || j<0 || grid[i][j]=='0'){
            return;
        }//범위 벗어나면 return, 순회 끝
        grid[i][j] = '0';
        dfs(grid,i,j-1);
        dfs(grid,i,j+1);
        dfs(grid,i-1,j);
        dfs(grid,i+1,j);
        return;
    }
}

배우게 된 점

💡 1) 본문에서 2중 for문 돌리며 최초 dfs 호출

-dfs에선 인덱스 i,j 받아서 +1 -1로 방향만 설정하여 순회 (훨씬 깔끔하다!!)

1. 조건문 순서의 중요성

-인덱스 범위 유효한지 ‘범위 체크’ 후에, 그 다음 ‘유효성 체크’해야 인덱스 오류 안뜬다.