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

• 백준 문제 URL

---

문제 요약

(N \times N) 지도에서 1은 집, 0은 빈 칸을 의미한다.
상하좌우로 연결된 1들의 묶음을 하나의 단지로 보고, 단지 개수와 각 단지에 속한 집의 수를 오름차순으로 출력하는 문제다.

---

핵심 아이디어

이 문제는 격자에서 연결 요소(Connected Component)를 찾는 전형적인 DFS/BFS 탐색 문제다.
전체 칸을 순회하다가 1을 발견하면 DFS를 시작하고, 탐색하며 방문 처리(1 → 0)를 해주면 같은 집을 중복해서 세지 않게 된다.
DFS 한 번이 끝날 때마다 “해당 단지의 집 개수”가 나오므로 이를 리스트에 저장한 뒤 정렬하면 된다.

---

알고리즘 핵심 로직

• 바깥쪽 이중 for문으로 모든 좌표 (i, j)를 탐색한다.
• map[i][j] == 1이면 새로운 단지 시작이므로 dfs(i, j)를 호출한다.
• dfs(x, y)에서는 현재 칸을 0으로 바꿔 방문 처리하고, 상하좌우로 이동 가능한 범위 내에서 1인 칸을 재귀로 방문하며 개수를 누적한다.
• DFS 결과(단지 크기)를 sizes에 넣고, 전체 탐색이 끝나면 sizes를 오름차순 정렬 후 출력한다.

---

전체 코드(제출용)

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

public class Main {
    static int[][] map;
    static int n;

    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];
        for (int i = 0; i < n; i++) {
            String line = br.readLine();
            for (int j = 0; j < n; j++) {
                map[i][j] = line.charAt(j) - '0';
            }
        }

        List<Integer> sizes = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (map[i][j] == 1) {
                    sizes.add(dfs(i, j));
                }
            }
        }

        Collections.sort(sizes);
        System.out.println(sizes.size());
        for (int a : sizes) {
            System.out.println(a);
        }
    }

    static int dfs(int x, int y) {
        map[x][y] = 0; // 방문 처리
        int count = 1;

        int[] dx = {-1, 1, 0, 0};
        int[] dy = {0, 0, -1, 1};

        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];

            if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
                if (map[nx][ny] == 1) {
                    count += dfs(nx, ny);
                }
            }
        }
        return count;
    }
}