2667번

2667번 - 단지번호붙이기

BFS 나 DFS 를 이용해서 각 구역에 대한 값들만 잘 지정해주면 되는 간단한 문제였다.

하지만 입력값을 평소처럼 int 형으로 받는게 아니라 

나 같은 경우에는 char 형으로 받아서 변환시켜서 넣어주었다.

입력하는 것에서 약간 당황스러웠지만, 좋은 경험이었다.

check 배열을 통해 방문하지 않은 곳은 0으로 , 방문한 곳은 그 구역에 따른 번호를 붙여주었다.

<정답 코드 - BFS , DFS 모두 포함 (사용하지 않는 함수는 주석 처리 필요)>

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
using namespace std;
 
int dx[4] = { 0,0,1,-1 };
int dy[4] = { 1,-1,0,0 };
int map[26][26];
int check[26][26];
int cnt;
int N;
vector<int> v;
void bfs()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (map[i][j] == 1 && check[i][j] == 0)
            {
                cnt++;
 
                queue<pair<int, int>> q;
                q.push(make_pair(i, j));
                check[i][j] = cnt;
 
                while (!q.empty())
                {
                    int now_x = q.front().first;
                    int now_y = q.front().second;
                    q.pop();
 
                    for (int d = 0; d < 4; d++)
                    {
                        int next_x = now_x + dx[d];
                        int next_y = now_y + dy[d];
                        if (next_x >= 0 && next_y >= 0 && next_x < N && next_y < N && check[next_x][next_y] == 0 && map[next_x][next_y]==1)
                        {
                            check[next_x][next_y] = cnt;
                            q.push(make_pair(next_x, next_y));
                        }
                    }
                }
            }
        }
    }
}
void dfs(int now_x,int now_y)
{
    check[now_x][now_y] = cnt;
 
    for (int d = 0; d < 4; d++)
    {
        int next_x = now_x + dx[d];
        int next_y = now_y + dy[d];
        if (next_x >= 0 && next_y >= 0 && next_x < N && next_y < N && check[next_x][next_y] == 0 && map[next_x][next_y] == 1)
        {
            dfs(next_x, next_y);
        }
    }
}
int main()
{
    
    cin >> N;
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            char a;
            cin >> a;
            map[i][j] = a - '0';
        }
    }
    //bfs
    bfs();
 
 
 
    //dfs
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (map[i][j] == 1 && check[i][j] == 0)
            {
                cnt++;
                dfs(i, j);
            }
 
        }
    }
    
 
    for (int k = 1; k <= cnt; k++)
    {
        int num = 0;
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                if (check[i][j] == k)
                {
                    num += 1;
                }
            }
        }
        v.push_back(num);
    }
 
    sort(v.begin(), v.end());
 
    cout << cnt << endl;
 
    for (int i = 0; i < v.size(); i++)
    {
        cout << v[i] << endl;
    }
 
}