[BOJ] 백준 2667 단지 번호 붙이기

출처:  https://www.acmicpc.net/problem/2667

 Input 

7

0110100

0110101

1110101

0000111

0100000

0111110

0111000

　 

 Output 

3

7

8

9

총 3개의 단지가 존재하며, 각 단지의 집의 수는 7, 8, 9개 입니다.

BFS 알고리즘을 이용해 배열을 순회하며 연결된 집을 처리.

---

import java.util.Collections;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
import java.util.Stack;
 
class House{
    int x,y;
    int number;
     
    public House(int x, int y, int number) {
        this.x = x;
        this.y = y;
        this.number = number;
    }
}
 
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
         
        int N = Integer.parseInt(sc.next());
        int[][] arr = new int[N+1][N+1];
         
        for(int i=1; i<=N; i++) {
            String str = sc.next();
            for(int j=1; j<=N; j++) {
                // char to int type
                arr[i][j] = str.charAt(j-1) - '0';
            }
        }
         
        Queue<House> queue = new LinkedList<>();
        // 각 단지수의 집 개수를 저장할 리스트
        Stack<Integer> houstCntList = new Stack<Integer>();
        // 동(오른쪽), 서(왼쪽), 남(아래), 북(위)
        int[] rowMove = {0, 0, 1 , -1};
        int[] colMove = {1, -1, 0 ,0};
         
        // 단지 numbering
        int number = 0;
         
        // 모든 집의 단지수가 매겨질 때까지
        while(true) {
            number++;
            House target = findUnNumberedHouse(arr, number);
            // 더이상 단지수를 매길 집이 존재하지 않는다면
            if(target == null) {
                number--;
                break;
            }
             
            // 해당 집과 연결된 모든 집에 대해 동일한 단지수를 매겨야 한다.(Queue에 데이터 저장)
            queue.add(target);
            // 해당 단지수에 우선 집이 한개 있는것으로 시작
            houstCntList.push(1);
            // 시작되는 탐색 위치의 집도 단지수가 매겨졌으므로 표시
            arr[target.x][target.y] = -1;
            while(!queue.isEmpty()) {
                House cur = queue.poll();
                for(int i=0; i<4; i++) {
                    // 다음 탐색 위치 (x,y 좌표)
                    int next_x = cur.x + rowMove[i];
                    int next_y = cur.y + colMove[i];
                     
                    // 배열 범위내에서
                    if(next_x > 0 && next_y > 0 && next_x <= N && next_y <= N ) {
                        // 아직 호수가 매겨지지 않은 집(House)라면...
                        if(arr[next_x][next_y] == 1) {
                            queue.add(new House(next_x, next_y, cur.number));
                            arr[next_x][next_y] = -1; // 단지수가 매겨진 집으로 표시
                             
                            //해당 단지수의 갯수를 올린다.
                            houstCntList.push(houstCntList.pop()+1);
                        }
                    }
                }
            }
        }
         
        System.out.println(number);
        // 오름차순 배열
        Collections.sort(houstCntList);
        for(int i=0; i<number; i++) {
            System.out.println(houstCntList.get(i));
        }
         
         
    }
 
    private static House findUnNumberedHouse(int[][] arr, int number) {
        int N = arr.length-1;
        int x=0, y=0;
         
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                if(arr[i][j] == 1) {
                    x = i;
                    y = j;
                    return new House(x,y, number);
                }
            }
        }
        // 모든 집의 단지수가 매겨졌다면 null 반환
        return null;
    }
}