[C++][백준] - 단지번호붙이기 (2667번)

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

2667번: 단지번호붙이기

🔔 문제 : 

입력값으로 (5<= N<= 25)인 N*N 크기의 지도가 주어집니다. 집이 있는곳은 1, 집이 없는 곳은 0을 숫자로 나타냅니다.

 

예를 들면

7
0110100
0110101
1110101
0000111
0100000
0111110
0111000

 

이때, 출력값으로 서로 붙어있는 단지들의 수를 출력하고, 단지내 집의 수를 오름차순으로 정렬하여 출력하는 문제입니다.

3
7
8
9

---

🔔 Kick Point :

BFS (너비 우선 탐색) 알고리즘을 사용해 단지내의 집들의 수를 구하였습니다.

 

N = 4인 지도가 아래 그림처럼 있습니다. (1은 집, 0은 비어있는 곳) 

totalArr[x][y] 이고, x 좌표 y좌표이고, totalArr[1][1]은 왼쪽 맨위 부터 시작합니다.

 

16(N*N)번만 검사할 예정입니다.

 

(1,1) 부터 (2,1) (3,1) ... (4,4) 까지 차례대로 검사할 예정이죠.

검사 할 때 빈집이 아니라 집이면 BFS()를 통과한 후에 단지를 구성합니다.

 

BFS() 통과후 -> 단지수(totalCnt) + 1 -> totalArr[단지수] = 7 -> 다시 검사

 

이런후에 BFS()를 통과하면서 단지수와, 단지내의 집의 갯수를 저장하고, 전체 지도를 다 훑어보는 방법을 사용합니다

 

 

그러면 BFS로 단지는 어떻게 구할까요?

Queue를 이용해서 구할것입니다.

 

이 큐에는 집인경우에만 들어갈 수 있고, 빠져나올경우 주변의 집 조사도 해줍니다.

이런 순서로 BFS를 진행하고 총 7개의 집들이 단지를 이루는 것을 알 수 있습니다.

 

 

이후에 totalArr[] 배열을 sort(start, end) 알고리즘을 통하여 오름차순으로 정렬해주고 출력해주면됩니다.

---

🔔 Code :

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

using namespace std;
int n, totalCnt = 0;
int totalArr[400] = { 0, };
bool map[27][27] = { {0,} };  // (x, y)
queue<pair<int, int>> q;

void BFS(int x, int y) {
	q.push(make_pair(x, y));
	map[x][y] = false;

	while (!q.empty()) {
		int _x = q.front().first;
		int _y = q.front().second;
		q.pop();
		totalArr[totalCnt]++;

		if (map[_x + 1][_y]) {
			q.push(make_pair(_x + 1, _y));
			map[_x + 1][_y] = false;
		}
		if (map[_x - 1][_y]) {
			q.push(make_pair(_x - 1, _y));
			map[_x - 1][_y] = false;
		}
		if (map[_x][_y + 1]) {
			q.push(make_pair(_x, _y + 1));
			map[_x][_y + 1] = false;
		}
		if (map[_x][_y - 1]) {
			q.push(make_pair(_x, _y - 1));
			map[_x][_y - 1] = false;
		}
	}
}

int main() {
	// Input
	cin >> n;

	for (int i = 0; i < (n * n); i++) {
		int x = i % n; x++;
		int y = i / n; y++;
		char tmp; cin >> tmp;

		if (tmp == '0') map[x][y] = false;
		else if (tmp == '1') map[x][y] = true;
	}

	// 전체탐색
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (map[j][i]) {
				++totalCnt;
				BFS(j, i);
			}
		}
	}

	// Output
	cout << totalCnt << endl;
	sort(totalArr + 1, totalArr + totalCnt + 1);
	for (int i = 1; i <= totalCnt; i++) {
		cout << totalArr[i] << endl;
	}
}

---