[BOJ] 2667. 단지번호붙이기

문제

www.acmicpc.net/problem/2667

2667번: 단지번호붙이기

---

해설

DFS 문제 풀이

---

코드

#include<iostream>
#include<algorithm>
#include<vector>
#include<string>
using namespace std;

int map[26][26];
int visit[26][26];
int n, cnt;
int dx[4] = { 1,-1,0,0 };
int dy[4] = { 0,0,1,-1 };

vector<int> q;

void dfs(int x, int y) {
	cnt++;
	visit[x][y] = true;

	for (int i = 0; i < 4; i++) {
		int nx = x + dx[i];
		int ny = y + dy[i];
		if (nx < 0 || nx >= n || ny < 0 || ny >= n) continue;
		if (map[nx][ny] == 1 && visit[nx][ny] == false) {
			dfs(nx, ny);
		}
	}
}

int main() {

	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);

	cin >> n;

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

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (map[i][j] == 1 && visit[i][j] == false) {
				cnt = 0;
				dfs(i, j);
				q.push_back(cnt);
			}
		}
	}

	sort(q.begin(), q.end());

	cout << q.size() << '\n';

	for (int i = 0; i < q.size(); i++) cout << q[i] << '\n';

	return 0;

}