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

문제 링크

2667번: 단지번호붙이기

풀이

BFS 문제

1. 방문하지 않았으면서 arr[i][j]가 1인 것을 찾아 bfs(i,j)를 실행한다.
2. bfs()를 실행하는 순간 집 하나가 포함되기 때문에 ans=1이 된다.
3. 이후는 다른 BFS 문제와 같이 큐를 이용한다. q에 push할 때마다 ans++를 해준다.
4. 단지 하나가 끝날 경우 answer에 ans를 push_back하고,
   answer.size()와 answer 값들을 출력하면 된다.

코드

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

using namespace std;

vector<vector<char>> arr;
vector<vector<int>> visit;

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

vector<int> answer;
int ans;

void bfs(int y, int x) {
	ans = 1;
	queue<pair<int, int>> q;
	q.push({ y,x });
	visit[y][x] = 1;
	while (!q.empty()) {
		int ny = q.front().first;
		int nx = q.front().second;
		q.pop();
		for (int i = 0;i < 4;i++) {
			int ty = ny + dy[i];
			int tx = nx + dx[i];
			if (ty < 0 || ty >= n || tx < 0 || tx >= n) continue;
			if (visit[ty][tx] == 0 && arr[ty][tx] == '1') {
				q.push({ ty,tx });
				visit[ty][tx] = 1;
				ans++;
			}
		}
	}
	answer.push_back(ans);
}

int main()
{
	cin >> n;

	arr.resize(n, vector<char>(n));
	visit.resize(n, vector<int>(n, 0));

	for (int i = 0;i < n;i++) {
		for (int j = 0;j < n;j++) {
			char c;
			cin >> c;
			arr[i][j] = c;
		}
	}

	for (int i = 0;i < n;i++) {
		for (int j = 0;j < n;j++) {
			if (arr[i][j] == '1' && visit[i][j] == 0)
				bfs(i, j);
		}
	}

	

	sort(answer.begin(), answer.end());
	cout << answer.size() << "\n";
	for (int i = 0;i < answer.size();i++) {
		cout << answer[i] << "\n";
	}

	return 0;
}