🏘️ BOJ 2667 단지번호붙이기

문제 요약

N×N 지도에서

• 1 → 집이 있는 곳
• 0 → 집이 없는 곳

상하좌우로 연결된 집들은 하나의 단지를 이룬다.

해야 할 일:

1. 전체 단지 개수를 구하고
2. 각 단지의 집 수를 오름차순으로 출력

---

핵심 개념

이 문제의 구조는 전형적인 2차원 BFS/DFS 영역 탐색 문제이다.

단지를 찾기 위해 필요한 조건

• 인접한 1들이 연결된 “덩어리” → 영역 탐색 문제
• 문제에서 “상하좌우"만 연결이라고 명시 → 대각선 X
• 단지마다 개수를 세어야 함 → BFS(또는 DFS)에서 count 증가

BFS가 필요한 이유

• 큐를 이용해 현재 위치에서 갈 수 있는 모든 ‘연결된 집’을 탐색
• 방문 체크로 중복 방문 방지
• 모든 단지를 탐색하기 위해 전체 map(N×N)을 훑으면서 BFS 시작 조건을 찾음

---

시간 복잡도 분석

지도 크기

• N ≤ 25
• 최대 칸 수: 25×25 = 625

모든 칸을 한 번씩만 방문한다.

💡 BFS 1회 시간

최대 625칸 → O(N²)

💡 BFS 시작점은 단지별로 다수일 수 있음

하지만 방문 체크 때문에
전체적으로 모든 칸은 단 한 번만 큐에 들어간다.

💡 전체 시간 복잡도

O(N²) = O(625)

연산량이 매우 적어서 Java·Python 모두 충분히 여유롭다.

---

풀이 흐름 정리

1. 입력을 받아 arr[][]에 저장

2. visited[][]로 방문 처리

3. (i, j)를 전체 순회하면서

   • 아직 방문하지 않고
   • arr[i][j] == 1인 지점이라면
     → 새 단지 시작 → BFS 실행

4. BFS에서 연결된 모든 집 카운트

5. 단지 수 + 단지 내 집 수 기록

6. 오름차순 정렬 후 출력

---

🔍 BFS 템플릿 핵심

Queue<int[]> q = new LinkedList<>();
q.add(new int[]{x, y});
visited[x][y] = true;

while (!q.isEmpty()) {
    int[] cur = q.poll();

    for (4방향) {
        좌표 유효성 검사
        1인지 검사
        방문했는지 검사
        → 조건 통과 시 q.add()
        → visited = true
        → count++
    }
}

---

✅ 최종 코드

package algo.ct.M11;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class BOJ_2667_단지번호붙이기_S1 {
    static int N;
    static boolean[][] visited;
    static int[][] arr;
    static int[] nx = {-1, 1, 0, 0};   // 상하좌우
    static int[] ny = {0, 0, -1, 1};
    static ArrayList<Integer> answer = new ArrayList<>();

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

        N = Integer.parseInt(br.readLine());
        arr = 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++) {
                arr[i][j] = line.charAt(j) - '0';
            }
        }

        // 전체 순회하며 단지 시작점 찾기
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < N; j++) {
                if (arr[i][j] == 1 && !visited[i][j]) {
                    int cnt = bfs(i, j);
                    answer.add(cnt);
                }
            }
        }

        Collections.sort(answer);
        System.out.println(answer.size());
        for (int cnt : answer)
            System.out.println(cnt);
    }

    // BFS로 단지 하나의 집 개수 세기
    public static int bfs(int x, int y) {
        visited[x][y] = true;
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x, y});
        int count = 1;

        while (!q.isEmpty()) {
            int[] cur = q.poll();
            int curX = cur[0];
            int curY = cur[1];

            for (int i = 0; i < 4; i++) {
                int nextX = curX + nx[i];
                int nextY = curY + ny[i];

                if (nextX < 0 || nextY < 0 || nextX >= N || nextY >= N) continue;
                if (visited[nextX][nextY]) continue;
                if (arr[nextX][nextY] == 0) continue;

                visited[nextX][nextY] = true;
                q.add(new int[]{nextX, nextY});
                count++;
            }
        }

        return count;
    }
}

---

💡 헷갈렸던 판단 부분

• BFS 반복문 안에서 count 증가하는 타이밍은? → q에 추가될 때 (= 실제로 방문할 때)

• 4방향 탐색은 while 문 안에 !!

• 시간복잡도!!!
  📌 “총 반복 횟수 × 한 반복에서의 처리 비용”
  그 결과가,

  🟢 1천만(10⁷) 이하 → 매우 여유로움
  🟡 1억(10⁸) 정도 → borderline (언어 따라 통과/시간초과 나뉨)
  🔴 10억(10⁹) 이상 → 대부분 시간초과

  ✔ 단지번호붙이기 같은 경우..
  N ≤ 25 → N² = 625
  여기서 BFS·DFS는 각 칸을 최대 한 번 방문

  ➤ 전체 연산량: 최대 625번
  O(N²) = 625

  625는 자바 기준으로
  1억 연산 중 0.0006% 정도밖에 안 됨.