백준 2667: BFS로 단지 수와 집 수 따로 세기

백준 2667번 ‘단지번호붙이기’는 단지의 수와 각 단지에 속한 집의 수를 모두 구하는 문제입니다. BFS로 연결된 집을 한 번에 탐색했습니다.

탐색을 시작한 횟수와 방문한 집 수를 나눕니다

지도를 차례로 확인하다가 값이 1이고 아직 방문하지 않은 칸을 만나면 새 단지로 보고 aptCnt를 늘린 뒤 BFS를 시작합니다.

BFS에서는 시작 집을 포함해 1부터 세고 새로운 집을 큐에 넣을 때마다 집 수를 늘립니다. 방문 표시는 큐에 넣을 때 하므로 같은 집을 여러 번 세지 않습니다. 탐색이 끝나면 반환한 집 수를 homeCnt에 저장했습니다.

단지의 수를 미리 알 수 없어 ArrayList를 사용했습니다. 모든 단지를 찾은 뒤에는 집 수를 오름차순으로 정렬해 출력했습니다.

당시 제출 코드

Java

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;
    }
}

배열로도 저장할 수 있을까

일반 배열로 구현하는 방법도 떠올렸습니다. aptCnt를 다 세기 전에 각 단지의 집 수를 다른 곳에 보관했다가 배열로 옮기는 식입니다. 다만 여기서는 그 방법을 구현하지 않고 단지를 찾을 때마다 바로 넣으면 되는 ArrayList를 사용했습니다.