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

---

풀이

1. BFS를 사용하여 풀었다.
2. 아파트 단지의 개수, 각 아파트 단지의 집의 개수를 세어야한다.
3. 아파트 단지의 개수를 세기 위해 bfs 메소드가 실행될 때마다 +1을 진행해준다.
4. 아파트 단지 내의 집의 수를 세기 위해 bfs를 진행하면서 큐의 입출력이 발생한 수만큼 +1을 해준다.
5. 아파트 단지의 개수가 정해져 있지 않기 때문에, ArrayList 자료형을 사용해서 아파트 내의 집 수를 저장해준다.

---

제출 코드

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

class Main {

    static int[][] map;
    static boolean[][] visited;
    static int N;
    static Queue<Pos> q = new LinkedList<>();
    static int[] opsX = {-1,1,0,0};
    static int[] opsY = {0,0,-1,1};
    static int aptCnt;
    static ArrayList<Integer> homeCnt = new ArrayList<>();
    static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

    static class Pos {
        int x;
        int y;

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());

        map = new int[N][N];
        visited = new boolean[N][N];

        for (int i = 0; i < N; i++) {
            String line = br.readLine();
            for (int j = 0; j < N; j++) {
                map[i][j] = line.charAt(j) - 48;
            }
        }
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] == 1 && !visited[i][j]) {
                    aptCnt++;
                    homeCnt.add(bfs(i,j));
                }
            }
        }
        Collections.sort(homeCnt);
        bw.write(aptCnt + "\n");
        for (int i : homeCnt) {
            bw.write(i+"\n");
        }
        bw.flush();
    }

    public static int bfs(int x, int y) {
        int max = 1;
        q.offer(new Pos(x, y));
        visited[x][y] = true;


        while (!q.isEmpty()) {
            Pos pos =q.poll();
            for (int i = 0; i < 4; i++) {
                int newX = pos.x - opsX[i];
                int newY = pos.y - opsY[i];

                if (-1 < newX && newX < N && -1 < newY && newY < N) {
                    if (map[newX][newY] == 1 && !visited[newX][newY]) {
                        q.offer(new Pos(newX, newY));
                        visited[newX][newY] = true;
                        max ++;
                    }
                }
            }
        }
        return max;
    }
}

---

후기

아파트 단지의 수가 정해져 있지 않기 때문에, ArrayList 자료형을 사용하였다고 하였는데...
뭔가 일반적인 배열로도 구현이 가능할지 모르겠다.
아파트 단지의 집의 개수를 aptCnt가 다 세어지기 전에 어디에 저장해두고 나중에 하나씩 저장하면 가능하지 않았을까 싶다(?)