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

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

2667번: 단지번호붙이기

 

 BFS 알고리즘을 사용하여 1을 만나면 연결된 모든 1들을 모두 탐색 후, 다음 1을 찾아서 연결된 모든 1들을 탐색하는 과정을 반복하면 됩니다. 

 

 BFS는 그래프를 탐색하는 과정에서 queue를 사용합니다. 

 

 이 문제에서 queue에 push 할 원소는 지도에서의 위치 좌표이기 때문에 편의를 위해 pair<int, int>를 pp로 typedef 해주었습니다. 

 

 map에서 '1'을 만나면 단지에 속하는 집의 수를 계산하는 변수 cnt를 0으로 초기화하고 '1'의 위치를 매개변수로 bfs를 호출합니다. 

 

 그럼 bfs()는 '1'에 연결된 모든 '1'들을 탐색 후 그 수를 return 합니다. 

 

 이때 return 값을 우선순위큐에 넣어 오름차순으로 정렬되게 해줍니다. :)

 

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

using namespace std;

typedef pair<int, int> pp;

int n;
priority_queue<int, vector<int>, greater<int>> ans; //단지의 속하는 집의 수 오름차순으로 정렬
char map[25][25]; //지도
int visit[25][25] = { 0, };  //탐색과정에서 방문표시할 배열
int cnt = 0; //각 단지에 속하느 집의 수 계산하기 위한 변수 

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

int bfs(int y, int x) {

	int tx, ty;
	queue<pp> q;
	pp temp;

	q.push({ y, x });  //시작 위치 push 
	visit[y][x] = 1; //방문 표시 

	while (!q.empty()) {
		temp = q.front();
		q.pop();
		cnt++;  //집의 수+1

		for (int i = 0; i < 4; i++) { //현재 위치에서 이동 가능한 위치(상, 하, 좌, 우)
			ty = temp.first + dy[i];
			tx = temp.second + dx[i];

			if (tx < 0 || tx >= n || ty < 0 || ty >= n)
				continue;
			if (map[ty][tx] == '0')
				continue;
			if (visit[ty][tx] == 1)
				continue;
			
			visit[ty][tx] = 1;
			q.push({ ty, tx });
		}
	}

	return cnt;
}

int main(void) {

	cin >> n;

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

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == '1' && visit[i][j] == 0) {
				cnt = 0;
				int ret = bfs(i, j);
				ans.push(ret);
			}
		}
	}

	cout << ans.size() << endl;

	while (!ans.empty()) {
		cout << ans.top() << endl;
		ans.pop();
	}

	return 0;
}