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

 

알고리즘 분류: 그래프 이론, 그래프 탐색, 깊이 우선 탐색, 너비 우선 탐색

문제 링크: https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

 

 

 

【 풀이 】

 

2차원 배열을 순회하면서 '1' 이 나왔을 때 모든 인접 접점을 방문하여 그 개수를 체크하는 문제이다.

즉 DFS, BFS 어느 것을 쓰든 무관하지만 여기선 BFS를 사용했다.

 

풀이 자체는 간단하다.

2차원 배열을 입력받고, 0부터 [n][n] 까지 순회하면서 '1' 이 적혀 있는 부분부터

그 부분을 방문하지 않았다면 BFS 를 하면 된다.

 

그리고 BFS 를 하면서 집의 개수는 cnt 변수에다 저장해 주고

cnt 변수는 따로 벡터에 push_back 하여 정렬하고 출력해 주면 끝.

 

 

【 코드 】

#include<iostream>
#include<algorithm>
#include<queue>
#define MAX 26
using namespace std;

struct Pos { int y, x; };
Pos front[4] = {
	Pos {-1,0},	// UP
	Pos {0,-1},	// LEFT
	Pos {+1,0},	// DOWN
	Pos {0,+1},	// RIGHT
};

int N, cnt;
vector<int>cnt_apart;

bool discovered[MAX][MAX];
char apart[MAX][MAX];

queue<Pos>q;

void Bfs(int y, int x) {
	Pos pos;
	pos.y = y;
	pos.x = x;

	discovered[y][x] = true;
	q.push(pos);
	cnt++;

	while (q.empty() == false) {
		pos = q.front();
		q.pop();

		if (pos.y == N && pos.x == N)
			break;

		for (int dir = 0; dir < 4; dir++) {
			Pos nextPos;
			nextPos.y = pos.y + front[dir].y;
			nextPos.x = pos.x + front[dir].x;

			if (nextPos.y >= 0 && nextPos.x >= 0		&&
				nextPos.y <= N && nextPos.x <= N	&&
				apart[nextPos.y][nextPos.x] == '1'	&&
				discovered[nextPos.y][nextPos.x] == false) 
			{
				discovered[nextPos.y][nextPos.x] = true;
				q.push(nextPos);
				cnt++;
			}
		}
	}
}

int main() {
	cin >> N;

	for (int y = 0; y < N; y++)
		for (int x = 0; x < N; x++)
			cin >> apart[y][x];

	for (int y = 0; y < N; y++)
		for (int x = 0; x < N; x++)
			if (apart[y][x] == '1' && discovered[y][x] == false) {
				cnt = 0;
				Bfs(y, x);
				cnt_apart.push_back(cnt);
			}

	sort(cnt_apart.begin(), cnt_apart.end());
	cout << cnt_apart.size() << endl;

	for (int i = 0; i < cnt_apart.size(); i++)
		cout << cnt_apart[i] << endl;

	return 0;
}