조건1: 1로 연결되어있는 것은 하나의 두더지방으로 취급한다.
조건2: 하나의 두더지방의 크기는 1의 개수이다.
조건3: 두더지방의 개수와, 내림차순으로 방의크기를 나열한다.
bfs알고리즘을 이용하여 풀기
bfs알고리즘의 기본원리는 아래코드와 같다.
인접리스트(노드를 이용한 연결)로 구성되어있다는 전제이다.
#include <queue>
bool visited[101];
using namespace std;
void bfs(int k)
{ queue<int> Q;
Q.push(k), visited[k] =1;
while(!Q.empty())
{
int current=Q.front(); Q.pop();
for(int i=0; i<G[current].size(); i++)
if(!visited[G[current][i]])
{
visited[G[current][i]]=1;
Q.push(G[current][i]);
}
}
}// 1. 탐색할 값 k를 큐에넣는다
// 2. k에 연결된 노드의 개수만큼 반복문을 통해 방문했는지 검사한다.
// 3. 만약 방문을 안했다면, visited에 방문처리를 한뒤 ,그값을 큐에 넣는다.
// 3-1. 만약 방문을 했다면 패스한다.
// 4. 큐에 모든값이 없어질때까지 1,2,3을 반복한다.
============================================================================================
예시
입력값
7
0 1 1 0 1 0 0
0 1 1 0 1 0 1
1 1 1 0 1 0 1
0 0 0 0 1 1 1
0 1 0 0 0 0 0
0 1 1 1 1 1 0
0 1 1 1 0 0 0
출력값
3
9
8
7
============================================================================================
// 1. 탐색할 값 k를 큐에넣는다
// 2. k에 연결된 노드의 개수만큼 반복문을 통해 방문했는지 검사한다.
// 3. 만약 방문을 안했다면, visited에 방문처리를 한뒤 ,그값을 큐에 넣는다.
// 3-1. 만약 방문을 했다면 패스한다.
// 4. 큐에 모든값이 없어질때까지 1,2,3을 반복한다.
============================================================================================
코드
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <string>
#include <stdlib.h>
#include <time.h>
#include <algorithm>
using namespace std;
struct VERTEX {
int a, b;
};
int A[101][101];
int Size[101];
int N;
int cnt = 0;
int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };
// 안전한 위치인지 확인
bool safe(int a, int b) {
return (a >= 0 && a < N) && (b >= 0 && b < N);
}
// 내림차순 비교 함수
int compare(int a, int b) {
return a > b;
}
// 입력 처리
void input() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
cin >> A[i][j];
}
}
}
// DFS로 연결된 영역을 탐색
void dfs(int i, int j, int c) {
queue<VERTEX> C;
VERTEX k;
C.push({ i, j });
A[i][j] = c;
Size[c - 2]++;
while (!C.empty()) {
k = C.front();
C.pop();
for (int z = 0; z < 4; z++) {
int nx = k.a + dx[z];
int ny = k.b + dy[z];
if (safe(nx, ny) && A[nx][ny] == 1) {
A[nx][ny] = c;
C.push({ nx, ny });
Size[c - 2]++;
}
}
}
}
// 문제 해결
void solve() {
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++) {
if (A[i][j] == 1) {
cnt++;
dfs(i, j, cnt + 1);
}
}
}
// 크기를 내림차순 정렬
sort(Size, Size + cnt, compare);
}
// 결과 출력
void output() {
printf("%d\n", cnt);
for (int i = 0; i < cnt; i++) {
printf("%d\n", Size[i]);
}
}
int main() {
cin >> N;
input();
solve();
output();
return 0;
}
