단지번호붙이기

문제

<그림 1>과 같이 정사각형 모양의 지도가 있다. 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다. 철수는 이 지도를 가지고 연결된 집들의 모임인 단지를 정의하고, 단지에 번호를 붙이려 한다. 여기서 연결되었다는 것은 어떤 집이 좌우, 혹은 아래위로 다른 집이 있는 경우를 말한다. 대각선상에 집이 있는 경우는 연결된 것이 아니다. <그림 2>는 <그림 1>을 단지별로 번호를 붙인 것이다. 지도를 입력하여 단지수를 출력하고, 각 단지에 속하는 집의 수를 오름차순으로 정렬하여 출력하는 프로그램을 작성하시오.

입력

첫 번째 줄에는 지도의 크기 N(정사각형이므로 가로와 세로의 크기는 같으며 5≤N≤25)이 입력되고, 그 다음 N줄에는 각각 N개의 자료(0혹은 1)가 입력된다.

출력

첫 번째 줄에는 총 단지수를 출력하시오. 그리고 각 단지내 집의 수를 오름차순으로 정렬하여 한 줄에 하나씩 출력하시오.

예제 입력 1

예제 출력 1

한 단지를 모두 셌을 때 다음 시작점을 찾기

지도에서 값이 1이고 아직 방문하지 않은 칸 하나를 만나면 새 단지의 시작점이다. 그 칸부터 상하좌우로 이어진 집을 BFS로 모두 찾고, 방문한 집 수를 기록한다. 예제의 최종 단지 크기는 정렬하면 7, 8, 9다. 대각선으로만 맞닿은 두 집은 연결되지 않으므로 서로 다른 단지가 될 수 있다.

코드는 좌표 (행, 열)을 행×N+열 정수 하나로 큐에 넣고 꺼낼 때 나눗셈과 나머지로 다시 복원한다. 새 이웃을 큐에 넣는 순간 seen을 true로 바꾸어 같은 집이 두 번 들어가지 않게 한다. BFS가 끝나면 해당 단지의 집 수가 확정되므로 목록에 추가한다. 바깥의 이중 반복은 모든 칸을 훑어 떨어진 단지까지 찾는다.

모든 칸을 한 번 훑고 집 하나마다 네 방향만 확인하므로 O(N²) 시간이다. 방문 배열과 큐는 최악 O(N²), 단지 크기 목록은 집 수 이하의 공간을 쓴다. 지도가 전부 0이면 단지 수 0만 출력한다. 한 집만 있는 단지도 크기 1로 기록한다. 기존 코드는 제출 클래스 이름이 Main이 아니어서 그대로 제출할 수 없었고, 정렬과 마지막 줄바꿈도 중복됐다.

예제 맨 위의 0110100에서 (0,1)과 (0,2)는 같은 단지다. (0,4)는 사이에 0이 있어 윗줄만으로는 연결되지 않지만, 아래 행들을 따라 다른 집과 이어지는지 탐색해야 한다. 한 줄을 읽으면서 연속한 1의 길이만 세면 단지를 정확히 찾을 수 없는 이유다.

이미지를 행렬로 읽을 때 첫 좌표는 행, 둘째는 열이다. 코드의 DR·DC 배열은 네 방향을 같은 인덱스로 묶는다. 예를 들어 첫 방향은 행+1, 열+0으로 아래 칸이다. 범위를 먼저 검사한 뒤 지도 배열을 읽어야 가장자리 집에서도 배열 밖 접근이 일어나지 않는다.

소스코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Queue;

public class Main {
    static final int[] DR = {1, -1, 0, 0};
    static final int[] DC = {0, 0, 1, -1};

    static int countHomes(char[][] map, boolean[][] seen, int row, int col) {
        int n = map.length;
        Queue<Integer> queue = new ArrayDeque<>();
        queue.add(row * n + col);
        seen[row][col] = true;
        int count = 0;
        while (!queue.isEmpty()) {
            int position = queue.remove();
            int r = position / n;
            int c = position % n;
            count++;
            for (int direction = 0; direction < 4; direction++) {
                int nr = r + DR[direction];
                int nc = c + DC[direction];
                if (nr < 0 || nr >= n || nc < 0 || nc >= n) continue;
                if (map[nr][nc] == '1' && !seen[nr][nc]) {
                    seen[nr][nc] = true;
                    queue.add(nr * n + nc);
                }
            }
        }
        return count;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(in.readLine());
        char[][] map = new char[n][];
        for (int row = 0; row < n; row++) map[row] = in.readLine().toCharArray();

        boolean[][] seen = new boolean[n][n];
        List<Integer> sizes = new ArrayList<>();
        for (int row = 0; row < n; row++) {
            for (int col = 0; col < n; col++) {
                if (map[row][col] == '1' && !seen[row][col]) {
                    sizes.add(countHomes(map, seen, row, col));
                }
            }
        }
        Collections.sort(sizes);
        StringBuilder out = new StringBuilder();
        out.append(sizes.size()).append('\n');
        for (int size : sizes) out.append(size).append('\n');
        System.out.print(out);
    }
}