[BOJ][C++] 백준 2667번: 단지번호붙이기

문제

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

 

문제 이해

• N × N 크기의 정사각형 지도에서 1은 집이 있는 곳을, 0은 집이 없는 곳을 나타낸다.
• 집이 있는 곳(1)끼리 상하좌우로 연결시켜 단지를 만든다.
• 총 단지수와 단지내 집의 수를 오름차순으로 출력한다.

 

문제 풀이

🔍 접근

집이 존재하는 곳을 기준으로 그 집의 상하좌우에 또 다른 집이 존재하는지를 판단하는 그래프 탐색 문제로 볼 수 있다.

지도를 순회하면서 '1'이 나왔을 때 모든 인접 정점을 방문하여 연결된 집의 개수를 구한다.

 

🔨 구현

BFS와 DFS를 이용하여 풀 수 있다.

• 방문 표기는 visited 배열을 만드는 대신 지도에서 방문한 곳을 '0'으로 바꾸어 표기할 수 있다.
• 집이 있는 곳에서 dr, dc 배열을 이용해서 상하좌우로 탐색한다.
• 다음 방문하는 곳에 집이 있으면 현재 단지의 집의 개수를 증가시킨다.
• 집이 없거나 방문한 곳(0)이면 연결되지 않은 곳으로, 탐색을 종료한다.
• 한 단지의 탐색이 끝나면 집의 개수를 저장하고 초기화한다.
• 단지 내 집의 수를 오름차순으로 출력하기 위해 정렬 함수를 사용한다.

 

🚨  탐색 시 인덱스 에러에 주의한다.

 

코드

1️⃣ BFS

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;
typedef pair<int, int> ci;

int bfs(int n, int r, int c, vector<vector<int>> &board) {
    int dr[4] = {-1, 1, 0, 0};
    int dc[4] = {0, 0, -1, 1};

    queue <ci> q;

    q.push({r, c});
    board[r][c] = 0;
    int cnt = 1;

    while (!q.empty()) {
        int cr = q.front().first;
        int cc = q.front().second;
        q.pop();

        for (int i = 0; i < 4; i++) {
            int nr = cr + dr[i];
            int nc = cc + dc[i];
            if (nr < 0 || nr >= n || nc < 0 || nc >= n || !board[nr][nc]) {
                continue;
            }
            q.push({nr, nc});
            board[nr][nc] = 0;
            cnt++;
        }
    }
    return cnt;

}

int main() {
    int n;
    string s;
    vector<int> ans;

    //입력
    cin >> n;
    vector<vector<int>> board(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        cin >> s;
        for (int j = 0; j < n; j++) {
            board[i][j] = s[j] - '0';
        }
    }

    //연산
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j]) {
                ans.push_back(bfs(n, i, j, board));
            }
        }
    }

    //출력
    cout << ans.size() << '\n';
    sort(ans.begin(), ans.end());
    for (int i: ans)
        cout << i << '\n';

    return 0;
}

 

 

2️⃣ DFS

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, cnt;
vector<vector<int>> board;
vector<int> ans;
int dr[4] = {-1, 1, 0, 0};
int dc[4] = {0, 0, -1, 1};

void dfs(int r, int c) {
    // 인덱스 에러 방지
    // 종료 조건: 집이 없거나 이미 방문한 곳
    if (r < 0 || r >= n || c < 0 || c >= n || !board[r][c]) {
        return;
    }

    cnt++;
    board[r][c] = 0;

    for (int i = 0; i < 4; i++) {
        dfs(r + dr[i], c + dc[i]);
    }
}

int main() {
    string s;

    //입력
    cin >> n;
    board.assign(n, vector<int>(n));
    for (int i = 0; i < n; i++) {
        cin >> s;
        for (int j = 0; j < n; j++) {
            board[i][j] = s[j] - '0';
        }
    }

    //연산
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (board[i][j]) {
                cnt = 0;
                dfs(i, j);
                ans.push_back(cnt);
            }
        }
    }

    //출력
    cout << ans.size() << '\n';
    sort(ans.begin(), ans.end());
    for (int i: ans)
        cout << i << '\n';

    return 0;
}