[dfs/bfs/체감난이도 하] 2667번 단지번호붙이기

dfs로 푼 문제

1,1 부터 n,n까지 검색하면서 1인곳부터 dfs를 시작한다 dfs를 시작후 깊이 들어가면서 1이라고 표시된곳을 0으로 고치고 1을 더해줌으로써 한 동의 몇개의 세대가 있는지를 체크한다.

알고리즘 자체는 오류가 없었으나 정적배열의 크기를 25*25로 잡고 int형으로 했더니 오류가 났던 문제 bool 26*26으로 수정했더니 잘 동작했다.

#include<iostream>
#include<vector>
#include<algorithm>
 
using namespace std;
bool W[26][26];
bool visited[26][26];
int diffx[4] = {1,0,-1,0};
int diffy[4] {0,1,0,-1};
vector<int> a;
 
int go(int x, int y)
{
    visited[x][y] = 1;
    W[x][y] = 0;
    int result = 1;
    for(int i=0; i<4; i++)
    {
        int nextX = x+diffx[i];
        int nextY = y+diffy[i];
        if(W[nextX][nextY] && !visited[nextX][nextY])
           result += go(nextX,nextY);
    }
    return result;
}
 
 
int main()
{
    int n;
    cin>>n;
    for(int i=1; i<=n; i++)
        for(int j=1; j<=n; j++)
            scanf("%1d",&W[i][j]);
    
    for(int i=1; i<=n; i++)
    {
        for(int j=1; j<=n; j++)
        {
            if(W[i][j])
            {
                a.push_back(go(i,j));
            }
        }
    }
    
 
    
    cout<<a.size()<<endl;
    sort(a.begin(),a.end());
    for(int i=0; i<a.size(); i++)
        cout<<a[i]<<endl;
    
    return 0;
}