[백준/C++] 백준 2667번: 단지번호붙이기

 

지금까지 엄청 쉬운 것만 풀다가 좀 막혔다... 

 

1) 왠만하면 input을 받을 때 string배열로 받자. (문자가 붙어서 나오는 map)

2) 이렇게 여러개를 그룹지어야 하는 경우 dfs를 여러번 돌려야한다.

3) vector로 단지마다의 가구수를 count해서 넣으면 vector의 size가 곧 단지 수..

 

 

String으로 받을 때,

 

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

//input
int N;
string map[26];

//output
int cnt = 0;
vector<int> people;

int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
void dfs(int x, int y) {

	for (int i = 0; i < 4; i++) {
		int next_x = x + dx[i];
		int next_y = y + dy[i];

		if (next_x < 0 || next_x >= N || next_y < 0 || next_y >= N) continue;
		if (map[next_x][next_y] == '1') {
			cnt++;
			map[next_x][next_y] = '2';
			dfs(next_x, next_y);
		}
	}

}
int main() {

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> map[i];
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j] == '1') {
				cnt = 1;
				map[i][j] = '2';
				dfs(i, j);
				people.push_back(cnt);
			}
			
		}
	}

	cout << people.size() << endl;
	sort(people.begin(), people.end());
	for (int i = 0; i < people.size(); i++) cout << people[i] << endl;



	return 0;
}

 

int배열로 받을 때,

 

#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;

//input
int N;
int map[26][26];

//output
int cnt = 0;
vector<int> people;

int dx[] = { 1, -1, 0, 0 };
int dy[] = { 0, 0, 1, -1 };
void dfs(int x, int y) {

	for (int i = 0; i < 4; i++) {
		int next_x = x + dx[i];
		int next_y = y + dy[i];

		if (next_x < 0 || next_x >= N || next_y < 0 || next_y >= N) continue;
		if (map[next_x][next_y] == 1) {
			cnt++;
			map[next_x][next_y] = 2;
			dfs(next_x, next_y);
		}
	}

}
int main() {

	cin >> N;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++)
		{
			scanf_s("%1d", &map[i][j]);
		}
	}

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j] == 1) {
				cnt = 1;
				map[i][j] = 2;
				dfs(i, j);
				people.push_back(cnt);
			}
			
		}
	}

	cout << people.size() << endl;
	sort(people.begin(), people.end());
	for (int i = 0; i < people.size(); i++) cout << people[i] << endl;



	return 0;
}