.leetcode(200. Number of Islands)

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

 

2. 2021.12.29 시도

소요시간: 24분(10분 구상, 14분 코딩)

class Solution {
    public int numIslands(char[][] grid) {
        if (grid.length == 0) {
            return 0;
        }
        
        int count = 0;
        for(int x=-1; x<grid.length; x++) {
            for(int y=0; y<grid[0].length; y++) {
                int size = checkIsland(grid, x, y);
                if (size > 0) {
                    count++;
                }
            }
        }
        
        return count;
    }    
    
    private int checkIsland(char[][] input, int x, int y) {
        if (x < 0 || y < 0 || x >= input.length || y >= input[0].length) {
            return 0;
        }
        if (input[x][y] == '0') {
            return 0;
        }
        if (input[x][y] == '-') {
            return 0;
        }
        
        input[x][y] = '-';
        int size = 1;
        size+=checkIsland(input, x+1, y);
        size+=checkIsland(input, x, y+1);
        size+=checkIsland(input, x-1, y);
        size+=checkIsland(input, x, y-1);
        
        return size;
    }
}

풀이 접근 과정

2차원 배열을 보고 문제를 이애하니 꼭 2차원 배열을 다 읽어야겠다는 생각이 들었다. 그러니 속도는 O(m*n)이 될 수 밖에 없고 배열 내의 요소를 2번 접근하지만 않으면 그건 최적의 풀이가 될거라는 확신을 갖게 되었다.

방향이 고민되었다. 4방향을 읽어서 확인할지 전진하는 방향으로만 읽을지 생각해보았다. 이런 것을 결정하는데는 어려운 샘플을 스스로 생각해보는게 좋은 돌파구가 된다. 결로적으로 4방향을 다 읽도록 결정했다. 동시에 지나온 곳은 따로 표시해서 다시 계산하는 일이 업어야겠다는 생각을 했다. 요소를 방문할 때 여러가지 방식이 있는데 나는 특수한 문자('-')로 표시했다.

이러다보니 준비물은 배열을 읽기위한 2차원 for문과 재귀함수 하나가 필요했다. 재귀함수와 항상 같이 오는건 종료조건이다. 종료조건은 3가지였다. 첫번째는 배열의 경계값을 넘을때, 두번째는 문제에서 정의한 '0'을 만났을 때, 세번째는 내가 정의한 '-'를 만났을 때이다. 나중에 생각든 거지만 문제에서 정의한 '0'로 '-'를 대체하면 더 간단해졌을 것이다.

섬의 갯수를 구할때는 섬의 크기를 재서 크기가 0보다 크면 섬 갯수를 올렸다. 이때 당시에는 한번 방문하지 않은 것만 재귀함수의 시작이라고 보았다면 재귀함수가 시작될때만 count해줄 수 있고 그러면 그것만으로도 섬의 갯수를 쉽게 구할 수 있겠다 싶었다. 하지만 문제풀때는 생각하지 못했다.

방향 배열을 선언해서 풀까도 고민했지만 dfs방식으로는 로직이 간단해서 따로 선언하지 않고 위에 처럼 나열식으로 재귀함수를 호출했다. 

 

느낀점

• 첫번재 시도보다 시간이 단축되었다. 생각이 조금 더 정리된 후에 코딩을 하니 좋았다.
• 풀이에서 사용한  '-'를 대시한여 문제에서 주어진 '0'을 사용하면 더 깔끔하게 정리되었겠다.
• 풀이에서는 size를 이용하여 섬여부를 확정했는데 for문에서 미리 validation check를 해서 2차원 for문내의 재귀함수가 시작되는 것은 새로운 섬이다라는 인식을 미리 했다면 좋았겠다.

class Solution {
    public int numIslands(char[][] grid) {
        if (grid.length == 0) {
            return 0;
        }
        
        int count = 0;
        for(int x=-0; x<grid.length; x++) {
            for(int y=0; y<grid[x].length; y++) {
                if (grid[x][y] == '0') {
                    continue;
                }

                checkIsland(grid, x, y);
                count++;
            }
        }
        
        return count;
    }    
    
    private void checkIsland(char[][] input, int x, int y) {
        if (x < 0 || y < 0 || x >= input.length || y >= input[0].length) {
            return;
        }
        if (input[x][y] == '0') {
            return;
        }
        
        input[x][y] = '0';

        checkIsland(input, x+1, y);
        checkIsland(input, x, y+1);
        checkIsland(input, x-1, y);
        checkIsland(input, x, y-1);
    }
}

• bfs로도 한번 풀어봤다.
  • bfs를 풀기위해서는 queue가 필수이다. java에서는 LinkedList를 이용해서 Queue기능을 이용할 수 있다.
  • bfs를 사용하면서 if문이 많아져 directions를 정의하고 좀 더 깔끔하게 코딩을 정리했다.
  • 2차원 배열은 고정적인 row,col 길이값이 나오는데 이를 전역변수로 두면 편리하다.
  • 가시적인 코딩을 선호하여 private method를 분리해서 풀었다.

class Solution {
    private int[][] directions = new int[][] {{1,0},{0,1},{-1,0},{0,-1}};
    private int rowLength;
    private int colLength;

    public int numIslands(char[][] grid) {
        if (grid.length == 0) {
            return 0;
        }
        
        rowLength = grid.length;
        colLength = grid[0].length;
        
        int count = 0;
        Queue<Integer> neighbors = new LinkedList<>();
        for(int x=-0; x<rowLength; x++) {
            for(int y=0; y<colLength; y++) {
                if (grid[x][y] == '0') {
                    continue;
                }

                count++;
                neighbors.add(toIndex(x, y));
                while(!neighbors.isEmpty()) {
                    int index = neighbors.remove();
                    int row = toRow(index);
                    int col = toCol(index);
                    
                    for (int d=0; d<directions.length; d++) {
                        int rowd = row + directions[d][0];
                        int cold = col + directions[d][1];
                        if (isInArray(rowd, cold) && grid[rowd][cold] != '0') {
                            grid[rowd][cold] = '0';
                            neighbors.add(toIndex(rowd, cold));
                        }   
                    }
                }
            }
        }
        
        return count;
    }    
    
    private int toIndex(int x, int y) {
        return x * colLength + y;
    }
    
    private int toRow(int index) {
        return index / colLength ;
    }
    
    private int toCol(int index) {
        return index % colLength;
    }
    
    private boolean isInArray(int x, int y) {
        if (x < 0 || y < 0 || x >= rowLength || y >= colLength) {
            return false;
        }
        
        return true;
    }
}

 

1. 2021.01.31 시도

소요시간: 80분

class Solution {
    public int numIslands(char[][] grid) {
        int height = grid.length;
        int width = grid[0].length;

        boolean[][] visited = new boolean[height][width];
        Set<Integer> duplicated = new HashSet<>();
        int ground = 0;
        for (int i=0; i<grid.length; i++) {
            for (int j=0; j<grid[0].length; j++) {
                if (visited[i][j]) {
                    continue;
                }
                if (grid[i][j] == '1') {
                    goIsland(grid, i, j, visited, ground);
                    ground++;
                }
            }
        }

        return ground;
    }

    private void goIsland(char[][] grid, int i, int j, boolean[][] visited, int ground) {
        if (i<0 || j<0 || i>=grid.length || j>= grid[0].length) {
            return;
        }

        if (visited[i][j]) {
            return;
        }

        visited[i][j] = true;
        if (grid[i][j] == '0') {
            return;
        }

        goIsland(grid, i, j+1, visited, ground);
        goIsland(grid, i+1, j, visited, ground);
        goIsland(grid, i-1, j, visited, ground);
        goIsland(grid, i, j-1, visited, ground);
    }
}

풀이 접근 과정

처음에는 순서대로 가고 떨어지는 당이 생기면 땅의 번호를 하나씩 증가하여 매기되, 번호가 다른땅이 이어지면 그 이어진 땅을 하나로 보려고 했다. 그러나 1시간이 지났어도 어느 부분인지 몰라도 자꾸 틀려서 아예 알고리즘을 바꿨다.그래서 아예 visisted라는 개념을 두어 방문한곳은 스킵하고 방문한 곳이라면 동서남북으로 타고타고 들어가도록 재귀를 만들었다. 종료조건은 0이거나 이미 범위를 넘었거나 방문했거나 이렇게 해서 말이다

 

느낀점

• 방문을 체크하니 확실히 금방 풀 수 있었다.
• 솔루션에서는 이걸 DFS라고 불렀다. 보통 DFS, BFS는 트리에서 많이 쓰이는데 이것을 트리처럼 본 것이다. 트리는 보통 하위노드가 2개로 되어있는 반면 지금 문제는 하위노드를 4개로 보고 마치 트리를 풀듯이 접근한 것이다. 이미 방문한 곳을 따로 메모리를 쓰지않고 '0'으로 바꾼건 센스인듯하다.
• 이를 BFS로도 풀 수 있다. 기본 동작은 똑같은데 다음 노드로 넘어가는 방식의 차이다.

---

알고리즘 정리노트: .leetcode(알고리즘 문제풀이 접근)

반응형