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

문제 링크: 2667번 단지번호붙이기

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

 

흔히 말하는 섬 개수와, 각 섬의 면적을 구하는 문제이다. 이 문제에서 섬 개수는 단지의 수, 각 섬의 면적은 각 단지의 집의 수를 뜻한다.

 

DFS 함수 진입 후, 해당 칸이 집이 없는 칸이라면 즉 map[row][col] != 1이라면 함수를 빠져나온다. 그렇지 않을 때에는 해당 칸을 '집이 있으며, 방문을 하였음'이라는 의미로 2로 바꾸어준다. 그리고 집이 있는 칸을 방문하였기에 면적을 1만큼 더해준다. 그 후 지도의 범위를 벗어나지 않는, 동서남북 방향의 칸에 대해서 DFS 함수를 호출하고, 호출된 함수가 반환하는 areaSize 값을 호출한 함수의 areaSize에 할당한다. 이렇게 하면 가장 처음에 호출된 DFS 함수는 해당 단지의 전체 면적을 반환한다. 이 때 반환된 면적이 1 이상이면 단지가 존재하는 것이므로 단지들의 크기를 저장해두는 리스트인 areaSizes에 추가해준다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {
    static int[] drow = {0, 0, 1, -1};
    static int[] dcol = {1, -1, 0, 0}; // 동서남북

    public static int dfs(int row, int col, int n, int[][] map, int areaSize) {
        if (map[row][col] != 1) return areaSize;

        map[row][col] = 2;
        areaSize++;

        for (int d = 0; d < 4; d++) {
            int nrow = row + drow[d];
            int ncol = col + dcol[d];
            if (nrow<0||ncol<0||nrow>=n||ncol>=n) continue;
            areaSize = dfs(nrow, ncol, n, map, areaSize);
        }

        return areaSize;
    }

    public static void main(String[] args) throws IOException {
        /* input */
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());

        int[][] map = new int[n][n];

        for (int i = 0; i < n; i++) {
            String t = br.readLine();
            for (int j = 0; j < n; j++)
                map[i][j] = (int)t.charAt(j) - '0';
        }

        /* logic */
        int areaNum = 0;
        ArrayList<Integer> areaSizes = new ArrayList<>();
        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                if (map[i][j] == 1) {
                    int cur = dfs(i, j, n, map, 0);
                    if (cur < 1) continue;
                    areaSizes.add(cur);
                    areaNum++;
                }
            }

        Collections.sort(areaSizes);
        StringBuilder sb = new StringBuilder();
        sb.append(areaNum).append("\n");
        for (int item : areaSizes)
            sb.append(item).append("\n");
        System.out.println(sb);
    }
}