[BOJ] 2267. 단지번호붙이기 - C++

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

 

#include <bits/stdc++.h>
using namespace std;

string board[26];
int apartment[26][26];
int dx[4] = { 0,1,0,-1 };
int dy[4] = { 1,0,-1 ,0};
int main() {

	int n;
	int count = 0; // 총 단지 수
	int house = 0; // 단지내 집의 수 
	queue<pair<int, int>> Q;
	vector<int> houseCount;
	cin >> n;

	for (int i = 0; i < n; i++) {
		cin >> board[i];
	}

	

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++) {
			
			if (board[i][j] == '0' || apartment[i][j]) continue;
			int house = 0; 
			apartment[i][j] = ++house; // 시작점 단지 증량
			Q.push({ i,j });
			count++;
			while (!Q.empty()) {
				
				pair<int, int> cur = Q.front();
				Q.pop();

				for (int dir = 0; dir < 4; dir++) {
					int nx = cur.first + dx[dir];
					int ny = cur.second + dy[dir];

					if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
					if (board[nx][ny] == '0' || apartment[nx][ny]) continue; // board[nx][ny]가 0일때 건너 뛰는거 항상 주의할 것.
					apartment[nx][ny] = ++house;
					Q.push({ nx,ny });
				}
			}
			houseCount.push_back(house);
		}
	}
	
	cout << count << endl;
	sort(houseCount.begin(), houseCount.end());

	for (int i = 0; i < count; i++) {
		cout << houseCount[i] << '\n';
	}

}

 

 

# 주의할 점

board[nx][ny]  == '0' 일 때 건너뛰는것이다.

계속 != 로 했어서 주의하자.

 

# 고려해야되는 부분

string이니까 이중포문을 돌지 않고

단일 포문으로 입력값을 받는다.

[i][j] 로 접근하면 문자만 접근이 가능하다.

Q 에 push전에 단지 증량을 해주면서 넣고

 

bfs가 끝나면 최대 단지내 집 수만 있을 것이다.

그 수를 벡터에 집어 넣는다

적절히 정렬하면 끝.