Leetcode[day17] - Number of Islands

Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example 1:

Input:
11110
11010
11000
00000

Output: 1

1. 알고리즘을 해결하기 위해서 생각한 방법

 

 - 우선, 문제를 이해하는데 시간이 좀 걸렸다.

 - 해당 문제는 0이 물이고, 1이 땅이라고 할 때, 이어진 1이 몇 개 있느냐? 라는 문제다.

다시 말해, 이어진 1은 섬이고, 0은 물이기에 몇 개의 섬을 구하느냐가 문제였다.

 - 해당 알고리즘은 고민 끝에 풀지 못 했다.

 

2. 알고리즘 작성 중, 어려운 점

 

 - 어려웠던 점은 단순히 for문을 이용하다 보니, index의 제한을 제한하는게 어려웠다.

 - 예를 들면, 마지막 인덱스의 오른쪽 섬을 탐색한다던지, 0 인덱스의 왼쪽 섬을 탐새해서 index오류를 띄웠고, 해당 문제를 제대로 해결하지 못 했다.

 - 그래서 이번에도 유튜버의 도움을 받았다.

 

3. 오늘도 도와주신 daose의 유튜브

 

https://www.youtube.com/channel/UCo9z7MWtndO_mZCXuPn8o_g

daose

4. 도움을 받아 작성한 알고리즘

 

class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        
        for(int i=0; i<grid.length; i++){
            for(int j=0; j<grid[i].length; j++){
                if(grid[i][j] == '1'){
                    mark(grid, i, j);
                    count++;    
                }
            }
        }
        return count;
    }
    
    private void mark(char[][] grid, int row, int col){
        grid[row][col] = '-';
        if(row < grid.length - 1 && grid[row+1][col] == '1'){
            mark(grid, row+1, col); // 상
        }
        if(row > 0 && grid[row-1][col] == '1'){
            mark(grid, row-1, col); // 하     
        }
        if(col > 0 && grid[row][col-1] == '1'){
            mark(grid, row, col-1); // 좌    
        }
        if(col < grid[row].length - 1 && grid[row][col+1] == '1'){
            mark(grid, row, col+1); //우    
        }
    }
}

5. 작성한 알고리즘 결과

 

6. 다른 사람이 작성한 알고리즘을 보고 배운점

 

 - 해당 문제를 풀기 위해서, for문을 row,col만큼 돌려준다.

 - 그리고 grid[row][col]이 1인지만, 단순하게 체크해준다.

 - 해당 조건에 성립한다면, 상하좌우의 1을 다른 문자로 바꿔주고, count를 올린다.

 - 상하좌우의 다른 문자를 바꾸기 위해서 재귀함수를 사용하는데, row-1, row+1, col-1, col+1과 같이 상하좌우 쉽게 이해할 수 있었다.

 

7. 반성할 점

 

 - 항상, 알고리즘은 일반적인 관점에서 생각해야 된다.

 - 재귀함수는 이해하기 쉬워야한다.

 

문제 : https://leetcode.com/explore/challenge/card/30-day-leetcoding-challenge/530/week-3/3302/

Explore - LeetCode