[백준] 2667번 단지번호 붙이기 (C++)

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

 

 

문제 설명

n x n 배열이 주어졌을 때, 연결된 컴포넌트를 찾는 문제이다.

 

주요 로직

1. 연결된 컴포넌트를 찾는다.
-> 리턴타입이 int인 dfs를 사용한다. 

 

정답 코드

#include <bits/stdc++.h>

using namespace std;

int n,cnt;
string str;
vector<int> v;
int arr[30][30], visited[30][30];
int dy[4] = {-1,0,1,0}, dx[4] = {0,1,0,-1};

int dfs(int y, int x){
	int num = 1;
	visited[y][x] = 1;
	for(int i=0; i<4; i++){
		int ny = y + dy[i];
		int nx = x + dx[i];
		if(ny < 0 || nx < 0 || ny > n || nx > n) continue;
		if(arr[ny][nx] == 0 || visited[ny][nx]) continue;
		num += dfs(ny,nx);
	}
	return num;
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> str;
		for(int j=0; j<n; j++)
			arr[i][j] = str[j] - '0';
	}
	
	for(int i=0; i<n; i++){
		for(int j=0; j<n; j++){
			if(arr[i][j] == 1 && !visited[i][j]){
				int a = dfs(i,j);
				cnt++;
				v.push_back(a);
			}
		}
	}
	
	sort(v.begin(), v.end());
	
	cout << v.size() << "\n";
	for(auto it : v) cout << it << "\n";
	
	return 0;
}