2667. 단지번호 붙이기

1. 해결방법

• BFS 이용해서 "한뭉텅이탐색" 
• map[][]을 입력받을 때, 집이 존재하는 위치에서 부터 BFS탐색하기

2. Solution

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

#define MAX 25
#define endl '\n'
using namespace std;

int dx[] = {0, 0, -1, 1};
int dy[] = {1, -1, 0, 0};

int N, total = 0;
int map[MAX][MAX];
bool visited[MAX][MAX];

vector<int> cnt;
vector<pair<int, int> > v;

void Input()
{
    cin >> N;
    
    int house;
    for(int i = 0; i < N; i++)
    {
        string Inp;
        cin >> Inp;

        for(int j = 0; j < N; j++)
        {
            int tmp = Inp[j]- '0';
            map[i][j] = tmp;
            if(tmp == 1) v.push_back(make_pair(i, j));
        }
    }
}

void BFS(int x, int y)
{
    queue<pair<int, int> > q;
    q.push(make_pair(x, y));
    visited[x][y] = true;

    int Cnt = 1;

    while(!q.empty())
    {
        x = q.front().first;
        y = q.front().second;
        q.pop();

        for(int d = 0; d < 4; d++)
        {
            int nx = x + dx[d];
            int ny = y + dy[d];

            if(nx >= 0 && nx < N && ny >= 0 && ny < N)
            {
                if(!visited[nx][ny] && map[nx][ny] == 1)
                {
                    q.push(make_pair(nx, ny));
                    visited[nx][ny] = true;
                    Cnt += 1;
                }
            }
        }
    }
    total += 1;
    cnt.push_back(Cnt);

}

void Solution()
{
    // BFS
    for(int i = 0; i < v.size(); i++)
    {
        int X = v[i].first;
        int Y = v[i].second;

        if(!visited[X][Y]) BFS(X, Y);
    }

    // 오름차순 정렬
    sort(cnt.begin(), cnt.end());

    // 출력하기
    cout << total << endl;
    for(int c = 0; c < total; c++)
    {
        cout << cnt[c] << endl;
    }
}

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

    Input();
    Solution();

    return 0;
}

 

3. 알아야 할 개념

• cin 문자열 입력받기

map[][] 입력 받을 때, 한 줄에 여러개의 값을 입력 받아야한다. 문자열을 입력받자

 

#include <string>

int map[N][N];

for(int i = 0; i < N; i++)
    {
    	// 문자열 입력받기
        string Inp;	
        cin >> Inp;

        for(int j = 0; j < N; j++)
        {
        	// 숫자 0은 아스키코드표를 보면, 문자 NULL('/0') 과 매핑되어 있다.
            int tmp = Inp[j]- '0';
            map[i][j] = tmp;
            if(tmp == 1) v.push_back(make_pair(i, j));
        }
    }