백준온라인저지(BOJ)/#2667/단지번호붙이기

https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

단지별로 house_count를 도입하여,

DFS가 재귀적으로 호출될 때마다 Call Stack에 쌓일때마다 house_cnt++로 풀면 될 것이다.

이렇게 한 세트의 DFS가 끝나면 다시 house_cnt를 0으로 하여, 다음 단지에 대해 house_cnt를 연산해준다. 

위의 포인트를 염두에 두고 2-Dim 좌표 공간에서는 DFS의 인자를 (y,x)로 놓고 쭉쭉 탐색해나갑시다.

---

구현 코드

#include <vector>
#include <iostream>
#include <algorithm>

using namespace std;
vector<string> board;

const int dy[] = {0, 0, -1, 1};
const int dx[] = {-1, 1, 0, 0};
int house_cnt;
int N;

void dfs(int y, int x){
    board[y][x] = '0';
    house_cnt++;
    for(int m = 0; m < 4; m++){
        //board[next_y][next_x]는 먼저 next_y ,next_x 좌표의 범위를 설정하고 다음줄에 꼭 적어야함
        if((y+dy[m])>=0 && (y+dy[m]<N)
           &&(x+dx[m])>=0 && (x+dx[m]<N)
           &&(board[y+dy[m]][x+dx[m]]=='1')){
            dfs(y+dy[m],x+dx[m]);
        }
    }
}

int main(){
    vector<int> house;
    cin>>N;
    for(int i = 0; i < N; i++){
        string s;
        cin>>s;
        board.push_back(s);
    }
    int count = 0;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            if(board[i][j]=='1'){
                house_cnt = 0;
                dfs(i,j);
                count++;
                house.push_back(house_cnt);
            }
        }
    }
    sort(house.begin(), house.end());
    
    cout<<count<<'\n';
    for(auto& i: house){
        cout<<i<<'\n';
    }
    return 0;
}