[leetcode] Number of Islands 정리

source 는 Github 에 있습니다.

문제 (Number of Islands)

• 문제

풀이

• 연결된 섬들은 1개로 count 합니다.
  • for 문을 2번 돌려서 순회를 하면 연결된 섬에 대해서 찾을 수 없습니다.
• 전체 grid 를 순회하면서 방문한 곳은 순회하지 않도록 구현해서 처리했습니다.
  • 순회할 때, DFS 를 써서 연결된 것들을 순회하게 했습니다.
  • 순회할 때는 상하좌우로 순회하게 했습니다.

source

    public int numIslands(char[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        visited = new boolean[m][n];
        int count = 0;
        for (int i = 0 ; i < m ; i++) {
            for (int j = 0 ; j < n ; j++) {
                if (visited[i][j] == false) {
                    count += numIslands(grid, i, j);
                }
            }
        }
        return count;
    }

    public int numIslands(char[][] grid, int x, int y) {
        int m = grid.length;
        int n = grid[0].length;
        int count = 0;
        if (m > x && x >= 0 && n > y && y >= 0 &&
                grid[x][y] == '1' && visited[x][y] == false) {
            count++;
            visited[x][y] = true;
            count += numIslands(grid, x, y + 1);
            count += numIslands(grid, x + 1, y);
            count += numIslands(grid, x - 1, y);
            count += numIslands(grid, x, y - 1);
        }
        return count > 0 ? 1 : 0; // 연결된 것들은 1개로 count
    }

복잡도

• 시간복잡도 : 섬을 한 번씩은 전부 순회해야하기에 O(n 제곱) 입니다. (grid 가 m*n 으로 이루어져있으므로)
• 공간복잡도 : 방문한 곳을 변수로 저장하기 위해 boolean 2차 배열을 (m * n) 사용했으니 O(n 제곱) 입니다.