백준 - 2667

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

class Main {
    static int N;
    static boolean[][] home;
    static boolean[][] visited;
    static int[][] dir = {
            {1,0},{-1,0},{0,1},{0,-1}
    };
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        home = new boolean[N][N];
        for(int i = 0; i < N; i++){
            String[] a = br.readLine().split("");
            for(int j = 0; j < N; j++){
                int num = Integer.parseInt(a[j]);
                if(num == 1) home[i][j] = true;
            }
        }
        visited = new boolean[N][N];

        int homes = 0;
        List<Integer> list = new ArrayList<>();
        for(int i = 0; i < N; i++){
            for(int j = 0; j < N; j++){
                if(!visited[i][j] && home[i][j]){
                    list.add(bfs(i,j));
                    homes++;
                }
            }
        }
        System.out.println(homes);
        Collections.sort(list);
        for(int cnt : list){
            System.out.println(cnt);
        }
    }
    static int bfs(int r, int c){
        int cnt = 1;
        visited[r][c] = true;
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(new int[] {r,c});

        while(!q.isEmpty()){
            int[] a = q.poll();
            int i = a[0]; int j = a[1];
            for(int d = 0; d < 4; d++){
                int nr = i + dir[d][0];
                int nc = j + dir[d][1];

                if(nr >= 0 && nc >= 0 && nc < N && nr < N){
                    if(!visited[nr][nc] && home[nr][nc]){
                        visited[nr][nc] = true;
                        q.offer(new int[] {nr,nc});
                        cnt++;
                    }
                }
            }
        }
        return cnt;
    }
}

풀이과정 및 리뷰

1. boolean[][] home - 1인 경우 true 저장하는 집 배열, boolean[][] visited - 방문 여부 저장할 배열, int[][] dir - 상하좌우 탐색할 배열, List<Integer> list - 단지별 집 수를 오름차순으로 정렬하기 위한 리스트 선언

2. bfs 내부에서 인접 4방향 탐색하며 방문하지 않았고&& home == true 인 경우 큐에 넣어가며 큐가 빌 때까지 탐색, 더이상 아무 인접 지점도 두 조건을 충족하지 못하는 경우 메서드 종료

3. 메인 메서드 내에서 2차원 배열 루프를 돌며 방문하지 않았고 && home == true인 경우 bfs를 호출하여 리턴값을 리스트에 저장 + 단지 수 카운트 homes++

   → 즉 메인 함수는 bfs가 인접지역에서 더이상 방문하지 않은 집을 못찾은 경우, 위치를 옮겨 다시 조건을 만족하는 지점을 찾아 탐색하기 위함임