[Algorithm] Leetcode 200. Number of Islands (java)

풀이 코드

 

class Solution {
    private static final int[][] DIRECTION = {
        {-1, 0}, {1, 0}, {0, -1}, {0, 1}
    };
    
    public int numIslands(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int ans = 0;
        
        for (int y = 0; y < m; ++y){
            for (int x = 0; x < n; ++x){
                if(grid[y][x] == '1'){
                    deleteIsland(y, x, grid);
                    ans++;
                }
            }
        }
        return ans;
    }
    
    public void deleteIsland(int y, int x, char[][] grid){
        
        if(y < 0 || y >= grid.length || x < 0 || x >= grid[0].length) return;
        if(grid[y][x] == '1'){
            grid[y][x] = '0';
            for(int[] direction : DIRECTION){
                int neighborY = y + direction[0];
                int neighborX = x + direction[1];
                
                deleteIsland(neighborY, neighborX, grid);
            }
        } 
    }
}

 

---

사고 과정

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

LeetCode - The World's Leading Online Programming Learning Platform

 

 

주어진 m X n의 binary grid "grid"의 "1"은 땅을, "0"은 물을 나타낸다. 

1이 모여있으면 섬, 0이 모여있으면 바다가 되는데, 이 중 섬의 개수를 구하는 문제!!

 

요즘 개발하면서 발생하는 문제들에 대해 일상 속 발생하는 문제와 연관지어서 해결법을 찾는 연습을 하고 있다. 

(생각보다 유용하다! 해보시길 추천..)

 

그런 의미에서 문제에 들어가기 앞서,, 우리가 평소 무언가 수를 셀 때 어떤 식으로 세는가?

주머니 속의 구슬을 셀 때는 count한 구슬은 밖으로 빼는 식으로 count한 것과 그렇지 않은 것을 구분하지 않는가? 

여기서 시작된 풀이법.. 

 

이 문제에서 섬을 세기 위해서 굳이 다른 grid를 생성해서 옮겨줄 필요는 없이, 그냥 섬을 없애면 되지 않을까??

(섬을 없앤다는 표현은 너무 섬뜩하니까.. 태평양 쓰레기 섬을 없앤다고 생각해보자!!)

문제의 궁극적 목표는 개수를 세는 것이니까!!

 

구현 시작.

 

먼저 grid 탐색을 위한 방향키부터 만들어주자. 

 

   private static final int[][] DIRECTION = {
        {-1, 0}, {1, 0}, {0, -1}, {0, 1}
    }

 

 

각각의 grid를 돌면서 만약 해당 인덱스값이 '1'이라면(즉, 섬이라면) 이를 '0'으로 바꿔주고(즉, 쓰레기 섬을 깨끗한 바다로 만들어주자!) 숫자를 카운트해주는 방향으로 구현해보자!

 

 public int numIslands(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int ans = 0;
        
        for (int y = 0; y < m; ++y){
            for (int x = 0; x < n; ++x){
                if(grid[y][x] == '1'){
                    deleteIsland(y, x, grid);
                
                    ans++;
                }
            }
        }
        return ans;
    }
    
    
    public void deleteIsland(int y, int x, char[][] grid){
    	// ~~~
        // 탐색 알고리즘으로 1을 0으로!!
        // ~~~
    }

 

이제 준비는 다 되었으니 searchIsland 메서드를 구현해주자!

 

public void deleteIsland(int y, int x, char[][] grid){
        
        if(y < 0 || y >= grid.length || x < 0 || x >= grid[0].length) return;
        if(grid[y][x] == '1'){
            grid[y][x] = '0';
            for(int[] direction : DIRECTION){
                int neighborY = y + direction[0];
                int neighborX = x + direction[1];
                
                deleteIsland(neighborY, neighborX, grid);
            }
        } 
}

 

 

탐색 범위를 넘어가는 경우에 대한 예외처리를 해주면서, 

해당 인덱스 값이 1이라면 0으로 바꿔주고 이를 재귀함수로 처리하자!!

 

이 과정들을 최종적인 코드는 다음과 같다. 

 

class Solution {
    private static final int[][] DIRECTION = {
        {-1, 0}, {1, 0}, {0, -1}, {0, 1}
    };
    
    public int numIslands(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        int ans = 0;
        
        for (int y = 0; y < m; ++y){
            for (int x = 0; x < n; ++x){
                if(grid[y][x] == '1'){
                    deleteIsland(y, x, grid);
                    ans++;
                }
            }
        }
        return ans;
    }
    
    public void deleteIsland(int y, int x, char[][] grid){
        
        if(y < 0 || y >= grid.length || x < 0 || x >= grid[0].length) return;
        if(grid[y][x] == '1'){
            grid[y][x] = '0';
            for(int[] direction : DIRECTION){
                int neighborY = y + direction[0];
                int neighborX = x + direction[1];
                
                deleteIsland(neighborY, neighborX, grid);
            }
        } 
    }
}

 

오알완!