Number of Enclaves

유승선 ·2024년 1월 23일
0

LeetCode

목록 보기
94/121

어렵지는 않은 문제다. 다만 생각은 좀 해야한다.

만약에 문제가 특정 범위 안에서의 어떤 구간을 원한다면은.. 그 범위내의 구간이 아니라 그 범위 밖에 구간을 보고 탐색하는게 좋은 방법일거 같다.

class Solution {
public:
    void dfs(vector<vector<int>>& grid, int i, int j){
        if(i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size() || grid[i][j] != 1) return; 
        grid[i][j] = 2; 

        dfs(grid,i+1,j);
        dfs(grid,i-1,j);
        dfs(grid,i,j+1);
        dfs(grid,i,j-1); 
    }
public:
    int numEnclaves(vector<vector<int>>& grid) {
        for(int i = 0; i < grid.size(); i++){
            for(int j = 0; j < grid[i].size(); j++){
                if(grid[i][j] == 1 && (i == 0 || j == 0 || i == grid.size()-1 || j == grid[0].size()-1)){
                    dfs(grid,i,j); 
                }
            }
        }

        int answer = 0; 
        for(int i = 0; i < grid.size(); i++){
            for(int j = 0; j < grid[i].size(); j++){
                if(grid[i][j] == 1) answer++; 
            }
        }
        return answer; 
    }
};
profile
성장하는 사람

0개의 댓글