백준 2667번: 단지번호붙이기

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

참고

BFS(Breadth-First Search): http://qlyh8.tistory.com/30?category=731166

BFS 문제: http://qlyh8.tistory.com/31?category=731166

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
 
public class Main {
    private static int N, count = 1;
    private static int[][] map;
    private static int[] dirX = {0, 1, 0, -1};
    private static int[] dirY = {1, 0, -1, 0};
 
    public static void main(String[] args) throws Exception {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(reader.readLine());
        map = new int[N][N];
 
        for(int i=0 ; i<N ; i++){
            String input = reader.readLine();
           for(int j=0 ; j<N ; j++){
               map[i][j] = input.charAt(j) - '0';
           }
        }
 
        for(int i=0 ; i<N ; i++){
            for(int j=0 ; j<N ; j++){
                if(map[i][j] == 1){ // 집이 있는 경우 탐색
                    bfs(new Position(i, j, ++count)); // 단지 번호가 2부터 시작 (1이랑 중복되면 안됨)
                }
            }
        }
 
        int[] danji = new int[count-1]; // 총 단지 수가 danji 배열의 총 크기
        for(int i=0 ; i<N ; i++){
            for(int j=0 ; j<N ; j++){
                if(map[i][j] > 1){ // 번호가 매겨진 단지
                    danji[map[i][j]-2]++; // 각 단지 내 집 수 계산
                }
            }
        }
 
        Arrays.sort(danji); // 오름차순 정렬
 
        StringBuilder builder = new StringBuilder();
        builder.append(count-1).append("\n");
        for (int aDanji : danji) {
            builder.append(aDanji).append("\n");
        }
 
        System.out.println(builder);
    }
 
    private static void bfs(Position position){
        Queue<Position> queue = new LinkedList<>();
        queue.offer(position);
 
        while(!queue.isEmpty()){
            Position front = queue.poll();
            map[front.getY()][front.getX()] = front.getCount(); // 단지 번호 갱신
 
            for(int i=0 ; i<4 ; i++){ // 집이 있는 곳의 주변 4방향 탐색
                int newY = front.getY() + dirY[i];
                int newX = front.getX() + dirX[i];
 
                if((0 <= newY && newY < N) && (0 <= newX && newX < N)){ // 지도 범위 내
                    if(map[newY][newX] == 1){ // 집이 있는 곳이면
                        map[newY][newX] = front.getCount(); // 단지 번호 갱신
                        queue.offer(new Position(newY, newX, front.getCount())); // 큐에 넣음
                    }
                }
            }
        }
    }
 
    public static class Position{
        int y, x, count;
 
        Position(int y, int x, int count) {
            this.y = y;
            this.x = x;
            this.count = count;
        }
 
        int getY(){return y;}
 
        int getX(){return x;}
 
        int getCount(){return count;}
    }
}