[C++] 백준 온라인 저지 2667번 단지번호붙이기 풀이

전형적인 BFS 문제로

정사각형 맵에서 연속되어 붙어 있는 집(1)들의 덩어리 갯수와

덩어리 안에 집이 몇개나 들어있는지 구하는 문제

 

---

문제의 조건

 

 

 

 

1. NxN 크기를 가진 정사각형 2차원 배열이 주어진다. 

 

2. 2차원 배열에는 0과 1이 들어있다. 

0은 아무것도 없는 곳을 뜻하고 1은 집이 있다는 것을 나타낸다. 

 

3. 1들이 상하좌우로 연속해서 붙어 있으면 같은 단지로 친다. 

주어지는 2차원 배열에는 단지가 여러개 있다. 

 

4. 첫 번째 줄에 주어진 2차원 배열에 들어 있는 단지의 갯수를 출력하고

두 번째 줄부터 각 단지 안에 있는 집의 갯수를 오름차순으로 정렬해서 출력하기 

 

---

풀이 과정

 

DFS 카테고리에 있긴 했지만 BFS로 풀어도 될 거 같아서 큐를 이용해 BFS로 풀었습니다. 

 

한 타일을 기준으로 상하좌우에 1이 있는 타일을 탐색하면서 넓이를 구한 뒤 

구한 넓이를 정답 배열에 추가하는 방식으로 코드를 짰습니다. 

 

---

 

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

using namespace std;

int main(int argc, const char * argv[])
{
    int N;
    cin >> N;
    
    //상하좌우 탐색할 방향값 
    vector<vector<int>> dir;
    dir.push_back({0,1});
    dir.push_back({0,-1});
    dir.push_back({1,0});
    dir.push_back({-1,0});
    
    //맵 입력 받기 
    vector<vector<int>> map(N, vector<int>(N, 0));
    for (int i = 0; N > i; i++)
    {
        string str;
        cin >> str;
        for (int j = 0; N > j; j++)
            map[i][j] = str[j] - '0';
    }
    
    vector<vector<bool>> visited(N, vector<bool>(N, false)); //방문 표시용 배열 
    vector<int> answers;
    for (int i = 0; N > i; i++)
    {
        for (int j = 0; N > j; j++)
        {
            //[i][j]번째 인덱스가 방문하지 않은 곳이고 집(1)이라면 BFS 시작 
            if (!visited[i][j] && 1 == map[i][j])
            {
                queue<pair<int, int>> q;
                int range = 0; //단지 넓이 
                q.emplace(make_pair(i, j));
                
                while (!q.empty())
                {
                    auto curPos = q.front();
                    q.pop();
                    
                    //현위치가 방문하지 않은 곳이고 집(1)이라면 
                    if (!visited[curPos.first][curPos.second]
                        && 1 == map[curPos.first][curPos.second])
                    {
                        range++; //단지 넓이 증가 
                        visited[curPos.first][curPos.second] = true; //방문 표시 
                        
                        //현위치 기준 상하좌우 방향에 방문 가능한 곳 탐색 
                        for (int k = 0; dir.size() > k; k++)
                        {
                            auto nextPos = make_pair(curPos.first + dir[k][0], curPos.second + dir[k][1]);
                            //다음 위치가 map 배열 인덱스 안이고 방문하지 않았고 집(1)이라면 큐에 추가 
                            if (0 <= nextPos.first && N > nextPos.first
                                && 0 <= nextPos.second && N > nextPos.second
                                && !visited[nextPos.first][nextPos.second]
                                && 1 == map[nextPos.first][nextPos.second])
                                    q.emplace(nextPos);
                        }
                    }
                }
                
                //위 과정이 끝나면 단지 하나에 대한 탐색이 끝남 
                //정답 배열에 넓이 저장 
                answers.emplace_back(range);
            }
        }
    }
    
    //오름차순 정렬 
    sort(answers.begin(), answers.end());
    
    //정답 배열 크기 출력 후 내용물 하나씩 출력 
    cout << answers.size() << endl;
    
    for (auto house: answers)
        cout << house << endl;
    
    return 0;
}

 

지금까지 BFS 문제 풀면서 처음으로 아무 힌트 없이, 가장 빨리 푼 문제입니다. 

역시 하다 보면 되는구나...ㅠㅠ

처음엔 BFS 증말증말 못 했었거든요...

계속 열심히 하자...!