백준 2667번 - 단지번호붙이기 c++

2667번: 단지번호붙이기

지도는 최대 25x25이며 1은 집이있는곳을, 0은 집이없는곳을 나타내고 1이 연결된 집들을 단지라고 한다.

출력은 단지의수와 단지내 집의수를 오름차순하는것이 문제입니다.

이 문제는 탐색알고리즘을 사용해야하며 저는 BFS알고리즘을 사용하였습니다.

 

일단 지도의 크기를 입력받고 2중for문으로 집을표시합니다.

입력이 완료되면 BFS알고리즘을 통해 단지의수와 집의크기를 구합니다.

여기서 cnt란 집의수를 말하는것으로 cnt=0으로 하여 한단지의 집의수를 구하면 다시 반복문으로 돌아가는데 이때 cnt=0으로 해주어야지만 단지별 집의수를 구할수 있습니다.

 

inside 함수를 정의해준이유는 x좌표와 y좌표가 지도밖으로 탐색하지않게 방지하게 하기위해서 입니다.

sort로 정렬을 하는이유는 오름차순으로 단지별 집의수를 나타내라고 하였기때문에 vector v에 저장된 집의수를 오름차순으로 정렬하여 출력합니다.

#include "pch.h"
#include <iostream>
#include <cstdio>
#include <stack>
#include <queue>
#include <utility>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>

#pragma warning(disable:4996)
using namespace std;

int map[25][25];
bool visited[25][25];
vector<int> v;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0,0, -1, 1};
int cnt;
int n;
int dan;
bool inside(int x, int y)
{
	return (x >= 0 && x <= n) && (y >= 0 && y <= n);
}

void bfs(int x, int y)
{
	cnt++;
	queue<pair<int, int>> q;
	q.push(make_pair(x, y));
	visited[x][y] = true;
	while (!q.empty()) {
		int qx = q.front().first;
		int qy = q.front().second;
		q.pop();
		for (int i = 0; i < 4; ++i) {
			int nx = qx + dx[i];
			int ny = qy + dy[i];
			if (map[nx][ny] == 1 && visited[nx][ny] == false && inside(nx, ny))
				bfs(nx, ny);
		}
	}
}


int main(void)
{
	cin >> n;
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			scanf("%1d", &map[i][j]);
		}
	}
	
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < n; ++j) {
			if (map[i][j] == 1 && visited[i][j] == false) {
				cnt = 0;
				bfs(i, j);
				v.push_back(cnt);
			}
		}
	}

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

	return 0;
}