[백준] 2667 단지번호붙이기

문제 설명

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

2667번: 단지번호붙이기

집이 있으면 1, 없으면 0을 나타내는 정사각형 모양의 지도가 있을 때, 연결된 집의 모임인 단지를 정의하고 단지에 번호를 붙이려한다

단지수와, 각 단지내 집의 수를 오름차순으로 정렬하기

 

문제 풀이법

모든 정점을 방문하는 문제이기에 dfs와 bfs 둘 다 사용할 수 있다

 

지도의 요소가 1이고 방문하지 않았으면 dfs와 bfs를 돌게된다

이때, 총 단지의 수는 + 1한다

dfs와 bfs를 돌면서 각 단지의 집 수를 + 1 하면서 각 단지의 모든 집을 다 세면, 그 값을 벡터에 넣는다

벡터에 넣은 수는 sort함수를 사용해 오름차순으로 정렬 후 출력한다

 

 

 

소스 코드

bfs

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

using namespace std;

int n;

int arr[26][26];
int visited[26][26];

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

int bfs(int y, int x)
{
    visited[y][x] = 1;
    
    queue<pair<int, int>> q;
    
    q.push({y, x});
    
    int cnt = 1;
    while (!q.empty())
    {
        int yy = q.front().first;
        int xx = q.front().second;
        q.pop();
        
        for (int i = 0; i < 4; i++)
        {
            int ny = yy + dy[i];
            int nx = xx + dx[i];
           
            if (ny < 0 || nx < 0 || ny >= n || nx >= n)
                continue;

            if (arr[ny][nx] == 0 || visited[ny][nx] == 1)
                continue;
        
            q.push({ny, nx});
            visited[ny][nx] = 1;
            cnt++;
        }
    }
    return (cnt);
}

int main()
{
    cin >> n;
    
    for (int i = 0; i < n; i++)
    {
        string str;
        
        cin >> str;
        for (int j = 0; j < n; j++)
        {
            arr[i][j] = str[j] - '0';
            visited[i][j] = 0;
        }
    }
    
    vector<int> v;
    int cnt = 0;
    
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (arr[i][j] == 1 && visited[i][j] == 0)
            {
                int tmp = bfs(i, j);
                v.push_back(tmp);
                cnt++;
            }
        }
    }
    
    sort(v.begin(), v.end());
    
    printf("%d\n", cnt);
    for (int i = 0; i < cnt; i++)
        printf("%d\n", v[i]);
    return 0;
}

 

dfs

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int n, sum;

int arr[26][26];
int visited[26][26];

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

void dfs(int y, int x)
{
    if (visited[y][x] == 1)
        return ;
    
    visited[y][x] = 1;
    sum++;
  
    for (int i = 0; i < 4; i++)
    {
        int ny = y + dy[i];
        int nx = x + dx[i];
           
        if (ny < 0 || nx < 0 || ny >= n || nx >= n)
            continue;

        if (arr[ny][nx] == 0 || visited[ny][nx] == 1)
            continue;
        dfs(ny, nx);
    }
}

int main()
{
    cin >> n;
    
    for (int i = 0; i < n; i++)
    {
        string str;
        
        cin >> str;
        for (int j = 0; j < n; j++)
        {
            arr[i][j] = str[j] - '0';
            visited[i][j] = 0;
        }
    }
    
    vector<int> v;
    int cnt = 0;
    
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            if (arr[i][j] == 1 && visited[i][j] == 0)
            {
                sum = 0;
                dfs(i, j);
                v.push_back(sum);
                cnt++;
            }
        }
    }
    
    sort(v.begin(), v.end());
    
    printf("%d\n", cnt);
    for (int i = 0; i < cnt; i++)
        printf("%d\n", v[i]);
    return 0;
}