💜 2667번 단지 번호 붙이기 JAVA

1. 문제 

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

2667번: 단지번호붙이기

2. 풀이에 대한 설명 

2차원 배열을 순회하면서,
(1) 1을 만난다면! 거기서 부터 해당 1의 상하좌우 중 붙어있는 1이 있는지 확인한다. (아파트 단지 내의 아파트 수 체크)
(2) 내가 금방 방문해서 확인한 1은 -1로 값을 바꾸어서 방문 처리한다. 
(3) 1 search가 끝나면 해당 아파트 단지의 아파트 수를 다 센 것이다. 

(4) 이때 아파트 수를 aptList라는 아파트 단지 별 아파트 수 체크하는 곳에 저장한다. 

(5) 이렇게 단지 별 아파트 수를 세면 된다. 

3. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static int [] idx = {-1,0,1,0};
    static int [] idy = {0,1,0,-1};

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        ArrayList<Integer> aptList = new ArrayList<>();

        // 1) 값 받기
        int N = Integer.parseInt(br.readLine());

        int [][] apart = new int[N][N];

        for (int i = 0; i < N; i++) {
            String s = br.readLine();
            for (int j = 0; j < N; j++) {
                apart[i][j] = Character.getNumericValue(s.charAt(j));
            }
        }

        // 2) 2차원 배열을 순회
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {

                int apartCnt = 0;

                // 3) 순회하다가 1을 만나면 사방탐색을 통해 근처의 아파트 단지 모두 검색 (한 번 검색한 방은 -1로 값을 바꾸기)
                if(apart[i][j] == 1){
                    ArrayDeque<Coordinate> aq1 = new ArrayDeque<>();
                    aq1.add(new Coordinate(i,j));
                    apart[i][j] = -1;

                    apartCnt++;

                    // 3-2) 사방 탐색
                    while (!aq1.isEmpty()){
                        Coordinate now = aq1.poll();

                        for (int k = 0; k < 4; k++) {
                            int nx = now.x + idx[k];
                            int ny = now.y + idy[k];

                            // 만약 사방 검색 값이 2차원 배열안에 들어가고, 그 값이 1이면
                            if(nx>=0 && ny>=0 && nx < N && ny < N  && apart[nx][ny] == 1){
                                // 값 추가
                                aq1.add(new Coordinate(nx,ny));
                                apart[nx][ny] = -1;
                                apartCnt++;
                            }
                        }
                    }

                    // 3-3) 1을 조우 후 BFS를 다 돌았다면, 아파트 단지 하나가 끝난 것이다.
                    // 따라서 해당 단지의 아파트 개수를 aptList에 넣는다.
                    aptList.add(apartCnt);
                }
            }
        }

        // 4) 모든 아파트 단지의 아파트 수를 출력
        Collections.sort(aptList);
        System.out.println(aptList.size());

        for(int temp : aptList){
            System.out.println(temp);
        }

    }

}

class Coordinate {
    int x;
    int y;

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