단지번호붙이기 (feat. 백준, 2667번)

단지번호붙이기
https://www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int N, arr[25][25], dx[4], dy[4], cnt;
bool visit[25][25];
bool dfs(register int x, register int y) {
	if (visit[x][y] || arr[x][y] == 0)		return false;
	visit[x][y] = true;
	for (register int d = 0, nx, ny; d < 4; ++d) {
		nx = x + dx[d], ny = y + dy[d];
		if (0 <= nx && nx < N && 0 <= ny && ny < N && !visit[nx][ny] && arr[nx][ny] == 1)
			++cnt, dfs(nx, ny);
	}
	if (cnt > 0)
		return true;
	return false;
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	priority_queue<int, vector<int>, greater<int>> ans;
	dx[0] = -1, dx[1] = 1, dx[2] = dx[3] = 0;
	dy[0] = dy[1] = 0, dy[2] = 1, dy[3] = -1;
	cin >> N;
	char tmp;
	for (register int i = 0, j; i < N; ++i)
		for (j = 0; j < N; ++j)
			cin >> tmp, arr[i][j] = tmp - '0', visit[i][j] = false;
	for (register int i = 0, j; i < N; ++i)
		for (j = 0; j < N; ++j) {
			cnt = 1;
			if (dfs(i, j))
				ans.push(cnt);
		}
	cout << ans.size() << "\n";
	while (!ans.empty())
		cout << ans.top() << "\n", ans.pop();
	return 0;
}
// *&)*@*

DFS 풀이 방법

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;
int N, arr[25][25], dx[4], dy[4], cnt;
bool visit[25][25];
bool bfs(register int x, register int y) {
	if (visit[x][y] || arr[x][y] == 0)		return false;
	visit[x][y] = true;
	queue<pair<int, int>> q;
	q.push(make_pair(x, y));
	while (!q.empty()) {
		auto v = q.front(); q.pop();
		x = v.first, y = v.second;
		for (register int d = 0, nx, ny; d < 4; ++d) {
			nx = x + dx[d], ny = y + dy[d];
			if (0 <= nx && nx < N && 0 <= ny && ny < N && !visit[nx][ny] && arr[nx][ny] == 1)
				++cnt, visit[nx][ny] = true, q.push(make_pair(nx, ny));
		}
	}
	if (cnt > 0)
		return true;
	return false;
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	priority_queue<int, vector<int>, greater<int>> ans;
	dx[0] = -1, dx[1] = 1, dx[2] = dx[3] = 0;
	dy[0] = dy[1] = 0, dy[2] = 1, dy[3] = -1;
	cin >> N;
	char tmp;
	for (register int i = 0, j; i < N; ++i)
		for (j = 0; j < N; ++j)
			cin >> tmp, arr[i][j] = tmp - '0', visit[i][j] = false;
	for (register int i = 0, j; i < N; ++i)
		for (j = 0; j < N; ++j) {
			cnt = 1;
			if (bfs(i, j))
				ans.push(cnt);
		}
	cout << ans.size() << "\n";
	while (!ans.empty())
		cout << ans.top() << "\n", ans.pop();
	return 0;
}
// *&)*@*

BFS 풀이 방법

 

연결된 집합이 총 몇개인지를 구하는 문제입니다.

따라서 BFS, DFS 모두 풀이가 가능한 문제입니다.