포스팅 목차
[입력]
첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.
7
0110100
0110101
1110101
0000111
0100000
0111110
0111000
[출력]
첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지 내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.
3
7
8
9
public class Main_단지번호붙이기 {
static int N;
static final int[] dr = new int[]{1,-1,0,0};
static final int[] dc = new int[]{0,0,-1,1};
public static void main(String[] args) throws Exception{
Scanner sc = new Scanner(System.in);
N = sc.nextInt();
sc.nextLine();
int[][] pan = new int[N+1][N+1];
for(int i=1; i<=N;i++){
char[] tmp = sc.nextLine().toCharArray();
for(int j=1; j<=N;j++){
pan[i][j] = (tmp[j-1] == '0'? 0:1);
}
}
int[] dangiCntArr = new int[N*N];
int[][] visit = new int[N+1][N+1];
int danginum = 1;
for(int i=1; i<=N;i++){
for(int j=1; j<=N;j++){
if(pan[i][j] == 1 && visit[i][j] == 0){
dangiCntArr[danginum-1] = bfs(pan, visit, new PairD(i, j, 0), danginum);
danginum = danginum +1;
}
}
}
System.out.println(danginum-1);
Arrays.sort(dangiCntArr);
for(int i=0; i<dangiCntArr.length; i++){
if(dangiCntArr[i] == 0) continue;
System.out.println(dangiCntArr[i]);
}
}
public static int bfs(int[][] pan, int[][] visit, PairD startPos, int danginum){
Queue<PairD> q = new LinkedList<PairD>();
q.add(startPos);
visit[startPos.r][startPos.c] = danginum;
int grp = 1;
while(!q.isEmpty()){
PairD p = q.remove();
for(int i=0; i<4;i++){
int pr = p.r + dr[i];
int pc = p.c + dc[i];
if(pr < 1 || pc < 1 || pr > N || pc > N){
continue;
}
if(pan[pr][pc] == 1 && visit[pr][pc] == 0){
q.add(new PairD(pr, pc, p.step+1));
visit[pr][pc] = danginum;
grp++;
}
}
}
return grp;
}
}
class PairD{
int r;
int c;
int step;
public PairD(int r, int c, int step){
this.r = r;
this.c = c;
this.step = step;
}
}
public class Main {
static int N;
static char[][] a;
static int[][] visit;
static int sol;
static int[] cnt;
static class st {
int i, j;
st(int a, int b) {
i = a;
j = b;
}
}
static st[] Queue;
static int Wp, Rp;
static void In_Queue(int i, int j) {
Queue[Wp++] = new st(i, j);
}
static st Out_Queue() {
return Queue[Rp++];
}
static int FF(int si, int sj) {
int house = 0;
int[] di = { -1, 1, 0, 0 };
int[] dj = { 0, 0, -1, 1 };
Wp = 0;
Rp = 0;
// 시작점을 큐에 넣기
In_Queue(si, sj);
visit[si][sj] = 1;
house++;
while (Wp > Rp) {
st out = Out_Queue();
for (int k = 0; k < 4; k++) {
int ni = out.i + di[k];
int nj = out.j + dj[k];
// 범위 초과이면 continue
if (ni < 1 || ni > N || nj < 1 || nj > N)
continue;
// 집이 아니면 continue
if (a[ni][nj] != '1')
continue;
// 방문했으면 continue
if (visit[ni][nj] == 1)
continue;
// 방문
In_Queue(ni, nj);
visit[ni][nj] = 1;
house++;
}
}
return house;
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
// 입력
N = sc.nextInt();
a = new char[N + 10][N + 10];
visit = new int[N + 10][N + 10];
cnt = new int[N * N + 10];
Queue = new st[N * N + 10];
for (int i = 1; i <= N; i++) {
a[i] = ("\0" + sc.next()).toCharArray();
}
// Flood Fill
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
if (a[i][j] != '1')
continue;
if (visit[i][j] == 1)
continue;
cnt[sol++] = FF(i, j);
}
}
// 오름차순 정렬
for (int i = 0; i < sol - 1; i++) {
for (int j = i + 1; j < sol; j++) {
if (cnt[i] > cnt[j]) {
int temp = cnt[i];
cnt[i] = cnt[j];
cnt[j] = temp;
}
}
}
// 출력
System.out.println(sol);
for (int i = 0; i < sol; i++) {
System.out.println(cnt[i]);
}
sc.close();
}
