[BOJ 2667번] (DFS/BFS) 단지번호붙이기 (C++)

단지번호붙이기 (Silver 1)

문제

전체 문제 보기

2667번: 단지번호붙이기

접근법

이 문제의 데이터 형식은 2차원 배열 형식으로 주어진다. 더 정확하게 따지면 문자열의 배열로 주어지고 있다. 입력 데이터인 0 또는 1이 같은 행일 경우 구분자 없이 입력되기 때문이다. 때문에 이 문제에서는 특별히 문자열을 파싱 하여 각 2차원 배열 노드에 값을 입력하는 부분이 추가로 구현되어야 한다. 데이터가 입력된 노드들에 인접 노드를 설정해주고 BFS 혹은 DFS를 사용하여 풀 수 있는 문제이다.

자료구조 선택

기본 각 집의 정보를 담을 Node 구조체를 다음과 같이 정의 하였다.

struct Node {
    Node(int num)   // 모든 노드는 노드에 할당된 번호(0 or 1)이 있어야 한다.
        : mNum(num)
        , mVisited(false)    // 방문 정보를 false로 초기화
    {}

    vector<Node*> mAdjacent;    // 인접 노드에 대한 정보
    int mNum;                   // 단지 번호 (0: 집이 없음, 1이상: 단지 정보)
    bool mVisited;              // 방문 정보
};

메인 함수에서는 2차원 벡터로 map을 선언하여 이 노드를 사용하였다.

// 단지 정보를 담을 2차원 벡터
vector<vector<Node*>> map;

문자열을 입력받고 0 또는 1의 정수로 파싱 하여 각각의 노드에 정보를 입력하는 부분은 다음과 같이 구현하였다.

// map에 단지 정보를 입력
map.resize(N);
for (int i = 0; i < N; ++i)
{
    map[i].resize(N);
    string input;
    cin >> input;
    for (int j = 0; j < N; ++j) 
    {
        map[i][j] = new Node(input[j] - '0');
    }
}

그리고 인접 노드를 설정해준 후 BFS 함수를 구현하여 각 단지 내의 집 수를 계산하였다. 추가적인 설명은 아래 전체 소스코드의 주석을 참고하자.

구현

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

#define endl '\n'
using namespace std;

struct Node {
    Node(int num)   // 모든 노드는 노드에 할당된 번호(0 or 1)이 있어야 한다.
        : mNum(num)
        , mVisited(false)    // 방문 정보를 false로 초기화
    {}

    vector<Node*> mAdjacent;    // 인접 노드에 대한 정보
    int mNum;                   // 단지 번호 (0: 집이 없음, 1이상: 단지 정보)
    bool mVisited;              // 방문 정보
};

// 시작 노드로부터 인접노드의 개수를 반환 BFS
// 한 번도 탐색되지 않은 단지 내에 있는 집의 총 수를 반환.
// 시작 노드를 탐색한 적이 있거나, 시작 노드에 집이 없을 경우 0 을 반환한다. 
int BFS(Node* begin)
{
    // 방문한 적이 있거나, 집이 없는 노드일 경우 0을 반환
    if (begin->mVisited == true || begin->mNum == 0)
        return 0;

    int cnt = 0;

    queue<Node*> q;
    q.push(begin);
    begin->mVisited = true;
    cnt++;  // 집 수 카운팅

    // 큐가 빌때 까지(탐색대상이 없을때 까지) 탐색
    while (!q.empty())
    {
        Node* cur = q.front();
        q.pop();

        for (auto neighbor : cur->mAdjacent)
        {
            // 방문한적이 없고, 집이 존재하는 경우(mNum이 1인 경우)
            if (neighbor->mVisited == false && neighbor->mNum == 1)
            {
                q.push(neighbor);
                neighbor->mVisited = true;
                cnt++; // 집 수 카운팅
            }
        }
    }

    return cnt;
}
int main() {
    // 입출력 성능 향상을 위한 설정
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);

    // N: 정사각형 지도의 가로(=세로) 크기 (5~25)
    int N;

    // 정답 출력을 위한 벡터
    vector<int> answer;

    // 단지 정보를 담을 2차원 벡터
    vector<vector<Node*>> map;

    cin >> N;

    // map에 단지 정보를 입력
    map.resize(N);
    for (int i = 0; i < N; ++i)
    {
        map[i].resize(N);
        string input;
        cin >> input;
        for (int j = 0; j < N; ++j) 
        {
            map[i][j] = new Node(input[j] - '0');
        }
    }

    // 각 노드의 인접한 노드를 설정한다.
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            if (i > 0)
            {
                map[i][j]->mAdjacent.push_back(map[i - 1][j]);
            }
            if (i < N - 1)
            {
                map[i][j]->mAdjacent.push_back(map[i + 1][j]);
            }
            if (j > 0)
            {
                map[i][j]->mAdjacent.push_back(map[i][j - 1]);
            }
            if (j < N - 1)
            {
                map[i][j]->mAdjacent.push_back(map[i][j + 1]);
            }
        }
    }

    // 모든 노드(집)을 기준으로 BFS 탐색을 진행한다.
    // BFS함수는 한 번이라도 탐색을 한 적 있거나, 집이 없다면 0을 반환하고
    // 집이 있는 경우 연결되어 있는 모든 집의 수를 반환한다.
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            int result = BFS(map[i][j]);
            if (result > 0)
                answer.push_back(result);
        }
    }

    // 정답을 정렬 한 후 요구사항에 맞게 출력
    sort(answer.begin(), answer.end());

    cout << answer.size() << endl;

    for (int a : answer)
    {
        cout << a << endl;
    }

    // 동적 할당된 노드들 삭제
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            delete map[i][j];
        }
        cout << endl;
    }
    return 0;
}