LeetCode - 200. Number of Islands

많이 봤던 문제 유형이다.

bfs 사용해서 풀면 될 것 같아서 구현했다.

conttinue할 조건 설정하는 데 디버깅 조금 걸렸다.

class Solution {
public:
    int dr[4] = {-1, 1, 0, 0};
    int dc[4] = {0, 0, -1, 1};
    int m, n;

    int numIslands(vector<vector<char>>& grid) {
        m = grid.size();
        n = grid[0].size();
        vector<vector<bool>> visited (m, vector<bool>(n, false));
        queue<pair<int, int>> q;
        int answer = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (visited[i][j] || grid[i][j] == '0') continue;
                answer++;
                q.push({i, j});
                visited[i][j] = true;
                while(!q.empty()) {
                    pair<int, int> cur = q.front();
                    q.pop();
                    for (int k = 0; k < 4; k++) {
                        int next_i = cur.first + dr[k];
                        int next_j = cur.second + dc[k];
                        if (next_i < 0 || next_i >= m || next_j < 0 || next_j >= n || visited[next_i][next_j] || grid[next_i][next_j] == '0')
                            continue;
                        q.push({next_i, next_j});
                        visited[next_i][next_j] = true;
                    }
                }
            }
        }

        return answer;
    }
};

첫 번째 풀이만에 속도도 빠르게 나왔고, 해설 보니까 맞는 풀이인 것 같다.

 

해설에선 dfs로 푸는 방법도 있었다.

class Solution {
private:
    int dir[4][2] = {
        {-1, 0},  // down
        {1, 0},   // up
        {0, -1},  // left
        {0, 1}    // right
    };

    void dfs(vector<vector<char>>& grid, vector<vector<bool>>& visited, int x, int y){
        for(int i = 0; i < 4; i++){
            int next_x = x + dir[i][0];
            int next_y = y + dir[i][1];

            if(next_x < 0 || next_x >= grid.size() || next_y < 0 || next_y >= grid[0].size())
            { 
                continue; 
            }else if(!visited[next_x][next_y] && grid[next_x][next_y] == '1'){
                visited[next_x][next_y] = true;
                dfs(grid, visited, next_x, next_y);
            }
        }
    }
public:
    int numIslands(vector<vector<char>>& grid) {
        int n = grid.size();
        int m = grid[0].size();

        vector<vector<bool>> visited(n, vector<bool>(m, false));

        int result = 0;

        for(int i = 0; i < n; i++){
            for(int j = 0; j < m; j++){
                if(visited[i][j] == false && grid[i][j] == '1' ){
                    result++;
                    cout<<result<<endl;
                    visited[i][j] = true;
                    dfs(grid, visited, i, j);
                }
            }
        }

        return result;
        
    }
};

왜인지 모르겠으나 dfs가 더 빨랐다.

그리고 해설에서는 visited를 따로 사용하지 않고 직접 grid를 바꾸는 방법을 썼다.