[백준] 2667번: 단지번호붙이기(BFS) - C++

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

2667번: 단지번호붙이기

 

---

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
using namespace std;

int N;
int map[25][25];
bool visited[25][25];
int dir[4][2]={{-1,0},{1,0},{0,1},{0,-1}};
queue<pair<int, int>> q;
vector<int> v;

void reset()
{
    for(int i=0;i<N;i++)
        for(int j = 0;j<N;j++)
        {
            map[i][j] = 0;
            visited[i][j] = 0;
        }
}

void BFS(int i, int j, int num)
{
    visited[i][j] = true;
    q.push(pair<int, int>(i,j));
    
    while (!q.empty())
    {
        i = q.front().first;
        j = q.front().second;
        q.pop();
        
        for(int d=0;d<4;d++)
        {
            int ni = i+dir[d][0];
            int nj = j+dir[d][1];
            
            if((ni>=0 && nj>=0)&&(ni<N && nj < N))
            {
                if(map[ni][nj] && !visited[ni][nj])
                {
                    visited[ni][nj] = 1;
                    q.push(pair<int, int>(ni,nj));
                    num++;
                }
            }
        }
    }
    v.push_back(num);
}

int main()
{
    cin>>N;
    reset();
    for(int i=0;i<N;i++)
    {
        string s;
        cin>>s;
        for(int j = 0;j<N;j++)
            map[i][j] = s[j]-'0';
    }
    
    int sum = 0;
    for(int i=0;i<N;i++)
    {
        for(int j = 0;j<N;j++)
        {
            if(!visited[i][j] && map[i][j]==1)
            {
                BFS(i, j, 1);
                sum++;
            }
        }
    }
    sort(v.begin(), v.end());
    cout<<sum<<endl;
    for(int i = 0;i<v.size();i++)
        cout<<v[i]<<endl;
            
}

<입력>

한줄씩 문자열로 입력받아 각 인덱스의 문자를 - '0' 을 통해 숫자로 바꾸어 map 배열에 저장해주었다.

 

<출력>

첫번째로 출력해야할 것은 총 단지수이다. 총 단지수를 구하는 것은 유기농 배추 문제에서 출력하는 result 값과 같은 방식으로 구하면 된다.

 

생각이 필요했던 것은 오름차순으로 각 단지내 집의 수를 출력하는 것이다.

단지의 수는 가변적이기 때문에 벡터 자료형을 사용하여 저장해주었다. 

오름차순으로 정렬하는 것은 해당 문제는 정렬이 주가 아니기 때문에 sort함수를 사용했다. (그래서 시간이 오래걸린듯,,?)

 

 

 

DFS로 푼 2667번

https://lin-ing-link.tistory.com/209

[백준] 2667번: 단지번호붙이기(DFS) - C++