[leetcode] Number of Islands

문제

• 문제 링크
• 지도를 나타내는 2차원 배열 grid가 주어진다. 값이 1인 곳은 땅을, 0인 곳은 물을 의미한다. 지도에 있는 섬의 개수를 구해야 한다. 섬은 물로 둘러쌓여 있고, 수직수평으로 땅이 연결된 곳을 의미한다.
• 제약 조건
  • grid 크기: 1 <= row, col <= 300

풀이

풀기 전

• grid를 순회하다가 땅을 만났을 때 섬에 포함되는 곳을 체크하면 된다. 그리고 다시 방문되지 않았으면서 땅인 곳을 찾아 순회한다. 섬에 포함되는지 체크하기 위해서는 DFS나 BFS를 사용할 수 있다.

코드

class Solution {
    private int[] dy = {-1, 1, 0, 0};
    private int[] dx = {0, 0, -1, 1};

	// DFS로 섬에 포함되는 땅을 방문 체크한다.
    private void DFS(char[][] grid, int y, int x) {
        int ny, nx;
        for (int i=0; i<4; i++) {  // 수직수평으로 한 칸씩 체크한다.
            ny = y + dy[i];
            nx = x + dx[i];

			// 연결된 곳이 범위를 벗어나거나 물이면 건너뛴다.
            if (ny < 0 || ny >= grid.length || nx < 0 || nx >= grid[0].length || grid[ny][nx] == '0')
                continue;
            
            // 땅을 물로 변경해주고 다시 탐색한다.
            grid[ny][nx] = '0';
            DFS(grid, ny, nx);
        }
    }

    public int numIslands(char[][] grid) {
        int ans = 0;

        int m = grid.length;
        int n = grid[0].length;
        for (int i=0; i<m; i++) {
            for (int j=0; j<n; j++) {
                if (grid[i][j] == '0')  // 물이면 건너뛴다.
                    continue;
                    
                // 땅을 만나면 물로 변경하여 방문 체크 해주고 탐색에 들어간다.
                grid[i][j] = '0'; 
                DFS(grid, i, j);
                ans++;
            }
        }
        return ans;
    }
}

푼 후

• DFS나 BFS를 구현할 수 있으면 쉽게 풀리는 문제였다.
• 모든 땅을 한 번씩 방문하므로 시간 복잡도는 O(row * col)이다. DFS에 사용하는 재귀 함수의 최대 깊이는 땅의 개수이므로 공간 복잡도도 O(row * col)이다.