• 유기농 배추 : 단지 번호 붙이기에서 단지 내 집 개수 세는 알고리즘을 빼면 해결되는 다운그레이드 문제
• 섬의 개수 : 단지 번호 붙이기에서 상하좌우 + 대각선 처리 과정까지 추가해주면 바로 해결되는 알고리즘

문제 이해

0과 1로 이루어진 2차원 배열이 존재한다.
이 때, 상하좌우에 1이 존재한다면 두 개의 1은 연결되어 있다라고 한다.
또한 모든 연결된 집의 집합을 1개의 단지로 표현할 수 있다.

이 때 단지의 개수를 구하라. 또한 단지마다 집의 개수를 오름차순으로 정렬해 출력하라.

문제 풀이

Array를 차례대로 순차하며 1을 발견할 때 마다 DFS나 BFS를 활용하여 연결된 모든 집들을 이었다.
이 때, DFS나 BFS를 통해 연결된 집에 방문하면 해당 집의 값을 1 ⇒ 0으로 바꾸어 다시 접근할 수 없도록 만들어줬다. 이를 통해 중복 문제를 해결했다.
마지막으로 Array에서 처음 1을 만날 때마다 단지 수 하나가 증가하는 것으로 생각하면 될 것이다.(연결된 모든 집들의 값은 0으로 바뀔 것이기 때문에 다음 Search에서는 절대 접근 불가)

이 문제에서는 단지내 집의 수도 구해야 한다.
따라서 DFS보다는 BFS를 통해 문제를 해결하였다.
BFS는 Queue를 사용하고, 재귀함수보다는 Queue를 통해 수를 세는 것이 조금 더 편리하기 때문이다.

Queue에 (중복되지 않는) 원소가 들어간 횟수만큼의 집 개수가 존재할 것이다.

코드

import java.io.*;
import java.util.*;

class Point{
	int x;
	int y;
	
	public Point(int x,int y) {
		this.x = x;
		this.y = y;
	}
}

public class Main {
	
	static int N;
	static int[][] house;
	static ArrayList<Integer> list = new ArrayList<>();
	
	static void bfs(int i, int j) {
		
		Queue<Point> points = new LinkedList<>();
		
		points.add(new Point(i,j));
		
		int num = 0;

		while(!points.isEmpty()) {
			Point tmp = points.poll();
			
			if(house[tmp.x][tmp.y]==0) continue;
            // 이미 이전에 인접해 있는 집으로 처리한 집 좌표이므로 
            // 따로 처리하지 않는다.
			
			house[tmp.x][tmp.y] = 0;
			num++;
			
			if(tmp.x!=0) points.add(new Point(tmp.x-1, tmp.y));
			if(tmp.y!=0) points.add(new Point(tmp.x, tmp.y-1));
			if(tmp.x<N-1) points.add(new Point(tmp.x+1, tmp.y));
			if(tmp.y<N-1) points.add(new Point(tmp.x, tmp.y+1));
		}
		
		list.add(num);
	}
	
	public static void main(String[] args) {

		FastReader sc = new FastReader();

		N = sc.nextInt();
		house = new int[N][N];
		int num = 0;
		
		for(int i =0;i<N;i++) {
			String tmp = sc.next();
			
			for(int j=0;j<N;j++) {
				house[i][j] = tmp.charAt(j)-'0';
			}
		}
		
		for(int i =0;i<N;i++) {
			for(int j =0;j<N;j++) {
				if(house[i][j]!=0) {
					num++;
					bfs(i, j);
				}
			}
		}

		Collections.sort(list);
		
		StringBuilder sb = new StringBuilder();
		sb.append(num).append("\n");
		
		for(int s:list) {
			sb.append(s).append("\n");
		}
		System.out.println(sb);
	}
	
	static class FastReader // 빠른 입력을 위한 클래스
}

결과