[BOJ/C++] 2667 단지번호붙이기 : BFS

문제

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

풀이

최단 경로 응용한 문제!

알고리즘 잘 짰는데 정작 틀린 이유는 정렬 안 해서;; 문제를 잘 읽자

🌹bfs 함수에서 cnt 배열 채울 때, 갈 수 있는 길이 2가지 이상이면 같은 숫자로 채워지는 것 주의

코드

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

using namespace std;

int N;
int map[25][25];
int cnt[25][25];
bool visited[25][25];

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

void bfs(int x, int y) {
	queue<pair<int, int>> q;

	visited[x][y] = true;
	cnt[x][y]++;
	q.push({ x, y });

	while (!q.empty()) {
		int xx = q.front().first;
		int yy = q.front().second;

		q.pop();
		for (int i = 0; i < 4; i++) {
			int nx = xx + dx[i];
			int ny = yy + dy[i];

			if (nx >= 0 && nx < N && ny >= 0 && ny < N && !visited[nx][ny] && map[nx][ny] == 1) {
				visited[nx][ny] = true;
				cnt[nx][ny] = cnt[xx][yy] + 1;
				q.push({ nx, ny });
			}
		}
	}
}

int search_max() {
	int max = 0;

	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (cnt[i][j] != 0) {
				max++;
			}
		}
	}

	return max;
}

void reflect() {
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (cnt[i][j] != 0) {
				map[i][j] = 0;
				cnt[i][j] = 0;
			}
		}
	}
}

int main() {
	vector<int> house;

	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) {
				bfs(i, j);
				int max = search_max();
				house.push_back(max);
				reflect();
			}
		}
	}

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

	return 0;
}