백준2667번: 단지번호 붙이기 / dfs & bfs

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
// 백준 2667 단지번호 붙이기
// 2차원 bfs로 풀이

int grid[26][26];
int check[26][26];
int block[700] = { 0, };

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

void bfs(int x,int y,int bcnt) {
	
	queue<pair<int, int>> q;
	q.push(make_pair(x, y));
	int acnt = 1;
	check[x][y] = bcnt;

	while (!q.empty()) {
		x = q.front().first; y = q.front().second;
		q.pop();
		for (int i = 0; i < 4; i++) {
			//넥스트 정점 방문
			int nx = x + dx[i]; int ny = y + dy[i];
			if (1 <= nx && nx <= n && 1 <= ny && ny <= n && grid[nx][ny]==1 && check[nx][ny]==0) {
				check[nx][ny] = bcnt; //방문여부 저장.
				q.push(make_pair(nx, ny)); //queue에 넣음
			}
		}
	}
}
int main() {
	cin >> n;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			scanf("%1d", &grid[i][j]);
		}
	}
	int bcnt = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (grid[i][j] == 1 && check[i][j] == 0) {
				bfs(i, j, ++bcnt);
			}
		}
	}
	cout << bcnt << endl;
	//단지별 아파트수 계산
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n;j++){
		block[check[i][j]]+=1;
	
	sort(block + 1, block + bcnt+1);

	for (int i = 1; i < 1 + bcnt; i++) {
		printf("%d\n", block[i]);
	}

	return 0;
}

bfs 구현. 아래는 dfs 구현으로 풀이했다. dfs구현이 pair 사용을 안하여도 되고 훨씬 간단하다.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
// 백준 2667 단지번호 붙이기
// dfs 구현
int grid[26][26];
int check[26][26];
int block[700] = { 0, };

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

void dfs(int x, int y, int bcnt) {

	check[x][y] = bcnt;

	for (int i = 0; i < 4; i++) {
		//넥스트 정점 방문
		int nx = x + dx[i]; int ny = y + dy[i];
		if (1 <= nx && nx <= n && 1 <= ny && ny <= n && grid[nx][ny] == 1 && check[nx][ny] == 0) {
			dfs(nx, ny, bcnt);
		}
	}
}

int main() {
	cin >> n;

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			scanf("%1d", &grid[i][j]);
		}
	}
	int bcnt = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (grid[i][j] == 1 && check[i][j] == 0) {
				dfs(i, j, ++bcnt);
			}
		}
	}
	cout << bcnt << endl;
	//단지별 아파트수 계산
	for(int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			block[check[i][j]] += 1;
		}
	}
	sort(block + 1, block + bcnt+1);

	for(int i = 1; i < 1 + bcnt; i++) {
		printf("%d\n", block[i]);
	}

	return 0;
}