183번째 문제 - 2667 단지번호붙이기

문제링크 : https://www.acmicpc.net/problem/2667

#include <iostream>

#include <algorithm>

#include <vector>

using namespace std;

int N, via[101][101];

//dfs 후에 connected component size return

int dfs(int y, int x)

{

if(y<0 || y>=N || x<0 || x>=N || via[y][x]==0) return 0;

else

{

via[y][x] = 0;

return 1 + dfs(y-1,x) + dfs(y+1,x) + dfs(y, x-1) + dfs(y, x+1);

}

}

int main(){

vector<int> ans;

//input

cin>>N;

for(int i=0; i<N;i ++)

{

for(int j=0; j<N; j++)

{

cin>>via[i][j];

}

}

//calc

for (int i = 0; i < N; i++)

{

for (int j = 0; j < N; j++)

{

if(via[i][j] == 1){

ans.push_back(dfs(i,j));

}

}

}

//output

sort(ans.begin(), ans.end());

cout<<ans.size();

for(int i=0; i<ans.size(); i++)

{

cout<<ans[i];

}

}

그냥 connected component 의 개수를 구하는 문제다.

dfs를 사용해 풀었음.