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

 

www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

[문제 풀이]

BFS를 이용하여 문제를 풀었습니다.

이 문제는 연결 된 단지의 총 개수와 집의 개수를 오름차 순으로 정렬하는 문제입니다. 단지의 연결 된 수를 찾는 것이 BFS 방법으로 할 경우 빠르다고 생각하여 BFS를 이용하여 문제를 해결했습니다.

 

코드 설명

• map을 순회하며 1이 있는 지점을 찾습니다.
• 1이 있는 지점인 경우 BFS 함수를 이용하여 연결 된 집의 개수를 찾습니다. 
• BFS 함수는 다음과 같습니다.
• 먼저 현재 지점을 방문 체크합니다.
• 그 후 상, 하, 좌, 우 방향에 방문하지 않은 집이 있다면 방문하고 집의 개수를 더해 줍니다.
• 더 이상 집이 없으면 집의 개수를 반환해 줍니다.

[코드]

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

using namespace std;

int n;

vector<string> map;
int visit[26][26];

int BFS(int x, int y) {

	int total = 1;

	visit[x][y] = 1;

	int dx[4] = { 0, 1, 0, -1 };
	int dy[4] = { 1, 0, -1, 0 };

	queue<pair<int, int>> que;
	que.push(make_pair(x, y));

	while (!que.empty()) {
		
		int temp_x = que.front().first;
		int temp_y = que.front().second;

		for (int i = 0; i < 4; i++) {
			int nx = temp_x + dx[i];
			int ny = temp_y + dy[i];

			if (nx < 0 || ny < 0 || nx >= n || ny >= n || visit[nx][ny] == 1 || map[nx][ny] == '0')
				continue;

			visit[nx][ny] = 1;
			que.push(make_pair(nx, ny));
			total++;
		}
		que.pop();

	}

	return total;
;
}

int main() {

	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;

	for (int i = 0; i < n; i++){
			string str; cin >> str;
			map.push_back(str);
		}
	
	vector<int> number;

	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			if (map[i][j] == '1' && visit[i][j] == 0)
				number.push_back(BFS(i, j));

	sort(number.begin(), number.end());
				
	cout << number.size() << endl;
	for (auto item : number)
		cout << item << endl;

	return 0;

}