[백준] 단지번호붙이기 2667 (silver 1) - c++

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

 

이 문제는
2차원 격자에서 연결된 컴포넌트(Connected Component)를 찾는 전형적인 문제다.

겉으로 보면 단순한 BFS 문제처럼 보이지만,
막상 구현하려고 하면 다음 지점에서 많이 막히게 된다.

• BFS를 어떻게 여러 번 호출하지?
• 각 단지가 몇 개의 집으로 이루어졌는지는 어디서 세야 하지?

나 역시 이 아이디어를 떠올리는 데 꽤 시간이 걸렸다.

---

문제 핵심 요약

• 1 → 집이 있는 곳
• 0 → 집이 없는 곳
• 상하좌우로 연결된 1들의 묶음이 하나의 단지
• 구해야 할 것
  1. 전체 단지 개수
  2. 각 단지에 포함된 집의 수 (오름차순 출력)

즉, 이 문제는
👉 “BFS 한 번 = 단지 하나” 라는 관점으로 접근해야 한다.

---

접근하면서 가장 어려웠던 점

처음에는 이런 생각까지는 하고 있었다.

• 단지 개수는 vector에 담아서 result.size()로 세면 되겠지
• 각 단지의 크기도 어딘가에 저장해야 한다

문제는 그걸 어디서 계산해야 하는지였다.

• BFS는 한 번만 도는 건가?
• 아니면 단지마다 BFS를 다시 호출해야 하나?
• BFS 함수 안에서는 뭘 계산하고, 밖에서는 뭘 해야 하지?

이 구조가 명확하지 않아서 계속 헷갈렸다.

---

핵심 아이디어

이 문제의 핵심 아이디어는 딱 하나다.

아직 방문하지 않은 집(1)을 발견할 때마다 BFS를 새로 시작한다

그리고 그 BFS는

• 하나의 단지만 탐색
• 그 단지에 포함된 집의 개수를 세서 반환

이렇게 역할을 나누는 것이다.

---

전체 탐색 구조

for(int i = 0; i < n; i++){
    for(int j = 0; j < n; j++){
        if(visited[i][j] || maps[i][j] == 0) continue;
        result.push_back(bfs(i, j));
    }
}

• 아직 방문하지 않은 1을 만나면
• bfs(i, j) 호출
• 반환값 = 해당 단지의 크기
• 이를 result에 저장

👉 BFS 호출 횟수 = 단지 개수

---

BFS 함수의 역할

BFS 함수는 한 단지에 대해서만 책임진다.

int bfs(int a, int b){
    queue<pair<int,int>> q;
    q.push({a,b});
    visited[a][b] = 1;

    int cnt = 0;

    while(!q.empty()){
        auto cur = q.front();
        q.pop();
        cnt++;

        for(int i = 0; i < 4; i++){
            int ny = cur.first + dy[i];
            int nx = cur.second + dx[i];

            if(ny < 0 || nx < 0 || ny >= maps.size() || nx >= maps.size())
                continue;
            if(visited[ny][nx] || maps[ny][nx] == 0)
                continue;

            visited[ny][nx] = 1;
            q.push({ny, nx});
        }
    }
    return cnt;
}

• 큐에서 하나 꺼낼 때마다 cnt++
• BFS가 끝나면
  • 그 단지의 집 개수 = cnt
• 이 값을 호출한 쪽에서 그대로 사용

---

왜 이런 구조여야 하는가?

이 구조를 쓰면 역할이 명확해진다.

• main 함수
  • 전체 격자 순회
  • BFS를 언제 시작할지 결정
  • 단지 개수 관리
• BFS 함수
  • 단지 하나 탐색
  • 해당 단지 크기 계산

그래서

• 단지 개수 → result.size()
• 단지별 크기 → result 내부 값

으로 자연스럽게 이어진다.

---

최종 출력

cout << result.size() << '\n';
sort(result.begin(), result.end());
for(int a : result){
    cout << a << '\n';
}

---

정리

• BOJ 2667은 BFS를 한 번만 쓰는 문제가 아니다
• BFS를 “단지 단위”로 여러 번 호출하는 문제다
• BFS 함수는
  • 탐색
  • 카운트
    두 역할만 맡기고
• 전체 구조는 바깥에서 관리하는 것이 핵심이다

이 관점을 잡고 나면
단지번호붙이기뿐 아니라
연결 요소 개수 / 영역 크기 문제들이 한 번에 정리된다.