백준 2667번 [단지번호붙이기](C++) -yes6686- 티스토리

백준 문제 풀이: 2667 [단지번호붙이기]

---

문제 링크: https://www.acmicpc.net/problem/2667

문제 설명:

n × n 크기의 지도를 입력받아 연결된 1의 그룹(단지)을 찾아 단지 수와 각 단지에 속하는 집의 수를 출력하는 프로그램을 작성하세요.

입력 조건:

• 첫 번째 줄에 지도의 크기 n이 주어집니다. (1 ≤ n ≤ 25)
• 다음 n개의 줄에는 '0'과 '1'로 이루어진 n개의 숫자가 주어집니다. (0은 집이 없음, 1은 집이 있음)

출력 조건:

• 첫째 줄에 총 단지 수를 출력합니다.
• 다음 줄부터 각 단지에 속하는 집의 수를 오름차순으로 출력합니다.

---

문제 해결 코드

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;

int n;
int arr[26][26];
int visited[26][26];
int dx[4] = {0, 0, 1, -1};
int dy[4] = {1, -1, 0, 0};
vector<int> blockSizes;

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

    int blockCnt = 1; // 현재 단지의 집 수

    while (!q.empty()) {
        int currX = q.front().first;
        int currY = q.front().second;
        q.pop();

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

            if (nx >= 1 && ny >= 1 && nx <= n && ny <= n && arr[nx][ny] == 1 && !visited[nx][ny]) {
                visited[nx][ny] = 1;
                q.push({nx, ny});
                blockCnt++;
            }
        }
    }

    blockSizes.push_back(blockCnt); // 단지 크기 저장
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    string row;

    for (int i = 1; i <= n; i++) {
        cin >> row;
        for (int j = 1; j <= n; j++) {
            arr[i][j] = row[j - 1] - '0';
        }
    }

    int blockCount = 0; // 총 단지 수

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (arr[i][j] == 1 && !visited[i][j]) {
                blockCount++;
                bfs(i, j);
            }
        }
    }

    sort(blockSizes.begin(), blockSizes.end()); // 단지 크기 오름차순 정렬

    cout << blockCount << '\n';
    for (int size : blockSizes) {
        cout << size << '\n';
    }

    return 0; // 프로그램 정상 종료
}

---

코드 설명

위 코드는 BFS를 사용하여 단지를 탐색하고 각 단지의 크기를 구합니다.

• 입력 처리:
  • 지도를 `arr` 배열에 저장합니다. 1은 집이 있는 곳, 0은 집이 없는 곳입니다.
• BFS 탐색:
  • 현재 단지의 집의 수를 `blockCnt`로 계산합니다.
  • 방문한 위치는 `visited` 배열에 표시하여 중복 방문을 방지합니다.
• 결과 처리:
  • 각 단지 크기를 `vector`에 저장하고, 이를 오름차순으로 정렬하여 출력합니다.

시간 복잡도 분석:

• 전체 탐색: O(n²).
• 정렬: O(k log k), k는 단지의 수.

최대 크기가 25 × 25이므로 효율적으로 동작합니다.

---

결과

다음은 입력 예시와 출력 결과입니다:

입력:
7
0110100
0110101
1110101
0000111
0100000
0111110
0111000

출력:
3
7
8
9

주어진 지도에서 총 3개의 단지가 존재하며, 각 단지의 크기는 오름차순으로 출력됩니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!