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

DFS로 문제 풀이

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

public class Main {
    private static int[][] map;
    private static int count;
    private static List<Integer> unit = new ArrayList<>();
    private static int[] xx = {1, -1, 0, 0};
    private static int[] yy = {0, 0, 1, -1};
    private static int N;

    public static void main(String[] args) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        map = new int[N][N];

        for (int i = 0; i < N; i++) {
            String[] row = br.readLine().split("");
            // StringTokenizer st = new StringTokenizer(row, "");
            for (int j = 0; j < N; j++) {
                // String nextToken = st.nextToken("");
                // System.out.println(nextToken+ "::nextToken::");
                map[i][j] = Integer.parseInt(row[j]);
            }
        }

        // start
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (map[i][j] == 1) {
                    dfs(i, j);
                }
            }
        }

        Collections.sort(unit);
        System.out.println(count);
        unit.forEach(System.out::println);
    }

    private static void dfs(int startX, int startY) {
        Queue<Point> queue = new LinkedList<>();
        count++; // 단지수 ++
        map[startX][startY] = 0;
        Point startPoint = new Point(startX, startY);
        queue.add(startPoint);
        int unitCount = 0; // 단지 내 집 수

        while (!queue.isEmpty()) {
            Point curPoint = queue.poll();
            unitCount++;

            for (int i = 0; i < xx.length; i++) {
                int nextX = curPoint.x + xx[i];
                int nextY = curPoint.y + yy[i];

                if (nextX >= 0 && nextX < N && nextY >= 0 && nextY < N && map[nextX][nextY] == 1) {
                    Point newPoint = new Point(nextX, nextY);
                    queue.add(newPoint);
                    map[nextX][nextY] = 0;
                }
            }
        }

        unit.add(unitCount);
    }

}


class Point {
    public int x;
    public int y;

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