[백준] 4963 섬의 개수

대각선이 포함하여 덩어리 개수를 세면 되는 문제이다.

 

상하좌우 덩어리를 세는 문제에서 활동 범위를 대각선으로만 늘리면 해결 할 수 있다.

 

□ bfs 버전

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> input4963(51,vector<int>(51,0));
vector<vector<bool>> check4963(51,vector<bool>(51,false));
queue<pair<int, int>> q4963;

void bfsIsland4963(int N, int M, int x, int y){
    int dx[] = {0,0,1,-1,1,-1,1,-1};
    int dy[] = {1,-1,0,0,1,1,-1,-1};
    
    while (!q4963.empty()) {
        int frontX = q4963.front().first;
        int frontY = q4963.front().second;
        q4963.pop();
        
        for(int i=0;i<8;i++){
            int mx = frontX + dx[i];
            int my = frontY + dy[i];
            
            if(mx<1 || my <1 || mx>M || my>N)
                continue;
            if(input4963[mx][my] == 1 && !check4963[mx][my]){
                check4963[mx][my] = true;
                q4963.push({mx,my});
            }
        }
    }
}

void islandCount4963(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    while(1){
        int a,b; cin>>a>>b;
        if(a == 0 && b == 0)
            break;
        
        for(int i=1;i<=b;i++)
            for(int j=1; j<=a; j++)
                cin>>input4963[i][j];
        
        int count = 0;
        for(int i=1;i<=b;i++){
            for(int j=1; j<=a; j++){
                if(!check4963[i][j] && input4963[i][j] == 1){
                    q4963.push({i,j});
                    check4963[i][j] = true;
                    bfsIsland4963(a, b, i, j);
                    count++;
                }
                
            }
        }
        cout<<count<<"\n";
        
        fill(input4963.begin(), input4963.end(), vector<int>(51,0));
        fill(check4963.begin(), check4963.end(), vector<bool>(51,false));
    }   
}

 

□ dfs 버전

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> input4963(51,vector<int>(51,0));
vector<vector<bool>> check4963(51,vector<bool>(51,false));

bool dfsIsland4963(int N, int M, int x, int y){
    
    if(x<1 || x>M || y<1 || y>N)
        return false;
    
    if(input4963[x][y] == 1 && !check4963[x][y]){
        check4963[x][y] = true;
        dfsIsland4963(N, M, x-1, y);
        dfsIsland4963(N, M, x+1, y);
        dfsIsland4963(N, M, x, y-1);
        dfsIsland4963(N, M, x, y+1);
        dfsIsland4963(N, M, x-1, y-1);
        dfsIsland4963(N, M, x+1, y+1);
        dfsIsland4963(N, M, x-1, y+1);
        dfsIsland4963(N, M, x+1, y-1);
        return true;
    }
    
    return false;
}

void islandCount4963(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    while(1){
        int a,b; cin>>a>>b;
        if(a == 0 && b == 0)
            break;
        
        for(int i=1;i<=b;i++)
            for(int j=1; j<=a; j++)
                cin>>input4963[i][j];
        
        int count = 0;
        for(int i=1;i<=b;i++){
            for(int j=1; j<=a; j++){
                if(dfsIsland4963(a, b, i, j)){
                    count++;
                }
            }
        }
        cout<<count<<"\n";
        
        fill(input4963.begin(), input4963.end(), vector<int>(51,0));
        fill(check4963.begin(), check4963.end(), vector<bool>(51,false));
    }
    
}