[LeetCode C++] 200. Number of Islands

⭐️ 난이도

Medium

---

⭐️ 문제

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

Number of Islands - LeetCode

크기가 m x n인 2차원 배열이 주어진다. '1'은 땅을 '0'은 물을 뜻한다.

이때, 섬의 개수를 구하시오.

 

섬은 물로 둘러싸여 있고, 수직/수평으로 인접한 땅을 이음으로서 형성된다.

또한 배열의 네 모서리가 모두 물로 둘러싸여 있다고 가정한다.

 

---

⭐️ Follow-up

X

 

---

⭐️ Idea flow

 

DFS, BFS로 풀 수 있는 유형의 문제였다.

DFS 혹은 BFS는 연결된 곳(이 문제에서는 상하좌우가 1인 곳)을 모두 방문 처리할 수 있다.

 

먼저 바깥 함수에서 이차원 vector를 돌면서 해당 칸이 '1'(육지)일 때 BFS를 실행한다.

BFS를 실행하면서 인접(상하좌우)한 칸이 '1'인 곳을 queue에 push하고, 해당 위치를 '2'로 변경하여 방문했다는 표시를 한다.

한 번의 BFS를 실행하고 나면 시작 위치와 연결된 땅들만 방문할 것이다.

따라서 BFS가 몇 번 실행되는지 그 횟수를 세면 섬의 개수를 알 수 있다.

 

---

⭐️ Code

class Solution {
public:
    int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1};

    void BFS(vector<vector<char>>& grid, int height, int width, int y, int x){
        queue<pair<int, int>> q;
        q.push({y, x});
        grid[y][x] = '0';

        while(!q.empty()){
            int cur_y = q.front().first;
            int cur_x = q.front().second;
            q.pop();

            for(int i = 0; i < 4; i++){
                int ny = cur_y + dy[i];
                int nx = cur_x + dx[i];
                if(((0 <= ny && ny < height) && (0 <= nx && nx < width)) && grid[ny][nx] == '1'){
                    q.push({ny, nx});
                    grid[ny][nx] = '2';
                }
            }
        }
    }

    int numIslands(vector<vector<char>>& grid) {
        int height = grid.size();
        int width = grid[0].size();
        int result = 0;


        for(int i = 0; i < height; i++){
            for(int k = 0; k < width; k++){
                if(grid[i][k] == '1'){
                    BFS(grid, height, width, i, k);
                    result++;
                }
            }
        }

        return result;
    }
};

 

 

---

⭐️ Feedback

 

BFS 말고 DFS로도 풀 수 있는 문제였는데, DFS가 시간적, 공간적 측면 모두 BFS보다 앞섰다.

BFS를 돌리기 위해서는 queue를 활용해야 하고 어쩔 수 없이 queue를 위한 메모리를 할당해야 한다.

 

하지만 DFS로 문제를 풀게 되면 queue를 위해 메모리를 할당하지 않아도 되기 때문에 메모리를 조금 더 아낄 수 있다.

BFS와 마찬가지로 방문한 곳은 '2'로 변경해주고 상하좌우를 DFS를 통해 검사하도록 한다.

 

위와 같이 DFS를 한 번 실행하고 나면 시작 위치에 연결된 땅들만 방문할 것이고, DFS의 실행 횟수를 세면 된다.

 

 

[전체 코드 보기]

class Solution {
public:
    void DFS(vector<vector<char>>& grid, int y, int x){
        if(y < 0 || y >= grid.size() || x < 0 || x >= grid[0].size()){
            return;
        }
        if(grid[y][x] == '2' || grid[y][x] == '0') 
            return;
        
        grid[y][x] = '2';
        DFS(grid, y + 1, x);
        DFS(grid, y, x - 1);
        DFS(grid, y - 1, x);
        DFS(grid, y, x + 1);
    }

    int numIslands(vector<vector<char>>& grid) {
        int height = grid.size();
        int width = grid[0].size();
        int result = 0;


        for(int i = 0; i < height; i++){
            for(int k = 0; k < width; k++){
                if(grid[i][k] == '1'){
                    DFS(grid, i, k);
                    result++;
                }
            }
        }

        return result;
    }
};