문제

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

풀이

Aha! (핵심)

• bfs 이용 --> 각 단지 내 집 개수 구하기

• 집 개수들을 vector에 저장.

• 벡터의 size 출력.
  오름차순 정렬 후 순서대로 출력.

어려웠던 점

• 입력받을 때, 띄어쓰기 없이 한 덩어리로 입력된다. 주의!
• 틀렸습니다 뜨는데 도통 이유를 모르겠다.
  거의 비슷하게 푸신 분을 봤는데, 그 분은 맞으셨던데... 맞는데 왜 틀렸지

코드

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

using namespace std;

int dr[4] = { -1, 1, 0, 0 }; //상하좌우
int dc[4] = { 0, 0, -1, 1 };

int map[25][25];

int countHouse(int r, int c, int N) { //bfs 이용
	queue<pair<int, int>> q;

	q.push({ r, c });
	map[r][c] = 0;
	int cnt = 1;

	while (!q.empty()) {
		int currR = q.front().first;
		int currC = q.front().second;
		q.pop();

		for (int k = 0; k < 4; k++) {
			int nr = currR + dr[k];
			int nc = currC + dc[k];

			if (nr < 0 && nc < 0 && N <= nr && N <= nc)
				continue;

			if (map[nr][nc] == 1) { //아직 방문x 이면
				q.push({ nr, nc });
				map[nr][nc] = 0; //방문했으므로 값 0으로 바꿈
				cnt++;
			}
		}
	}

	return cnt;
}

int main() {
	int N; cin >> N;
	vector<int> result; //각 단지의 집 개수

	/*입력*/
	for (int i = 0; i < N; i++) {
		int input; cin >> input; //행을 한꺼번에입력
		for (int j = N - 1; j >= 0; j--) {
			map[i][j] = input % 10;
			input /= 10;
		}
	}

	/*수행*/
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++) {
			if (map[i][j] == 1) {
				result.push_back( countHouse(i, j, N) );
			}
		}
	}
	

	/*출력*/
	cout << result.size() << "\n";

	sort(result.begin(), result.end());
	for (int cnt : result) {
		cout << cnt << "\n";
	}

	return 0;
}