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

일단 이 문제는 DFS, BFS 둘 다 가능하지만, 저는 BFS를 선호하기 때문에 BFS로 풀었습니다

1. 입력된 맵정보를 2차원 for문으로 순회하면서 맵이 1인 부분에서 BFS로 영역을 탐색

2. BFS 탐색이 한번 끝날 때 마다 카운트를 올려주면서 영역의 갯수를 구해주면 끝

ICT코테는 영역의 넓이를 구하라고 되어 있는데 이것도 BFS 내부에서 마킹할 때 마다 카운트를 세주면 되는 간단한 문제!

그래도 혹시 모르니 DFS, BFS문제 모두 올리겠습니다

- BFS버전

#include <iostream>
#include <stdio.h>
#include <algorithm>
#define MX 30
 
using namespace std;
 
struct kkk {
    int x, y;
}q[MX * MX];
 
int map[MX][MX], check[MX][MX], arr[MX * MX];
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
int N, num;
 
void bfs(int x, int y)
{
    int st, ed, ix, iy, nx, ny;
    st = ed = -1;
    q[++st].x = x; q[st].y = y;
    check[y][x] = num;
 
    while (st != ed)
    {
        ix = q[++ed].x; iy = q[ed].y;
        for (int i = 0; i < 4; i++)
        {
            nx = ix + dx[i]; ny = iy + dy[i];
            if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
            if (!map[ny][nx] || check[ny][nx]) continue;
            q[++st].x = nx; q[st].y = ny; check[ny][nx] = num;
        }
    }
}
 
int main(void)
{
    cin >> N;
 
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            scanf("%1d", &map[i][j]);
 
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (!check[i][j] && map[i][j])
            {
                num++;
                bfs(j, i);
            }
        }
    }
 
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            if (check[i][j]) arr[check[i][j]] += 1;
 
    sort(arr, arr + (num + 1));
 
    cout << num << endl;
 
    for (int i = 1; i <= num; i++)
        cout << arr[i] << endl;
 
    return 0;
}

- DFS 버전

#define CRT_SECURE_NO_WARINGS
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <algorithm>
#define MX 30
 
using namespace std;
 
int map[MX][MX], check[MX][MX];
int M, num[MX*MX], d = 1;
int dx[] = { -1, 1, 0, 0 };
int dy[] = { 0, 0, -1, 1 };
 
void dfs(int x, int y, int d)
{
    if (map[y][x] == 0 || check[y][x] != 0) return;
 
    check[y][x] = d; num[d]++;
 
    for (int i = 0; i < 4; i++)
    {
        if (x + dx[i] <= 0 || y + dy[i] <= 0 || x + dx[i] > M || y + dy[i] > M) continue;
        if (check[y + dy[i]][x+dx[i]] != 0) continue;
        dfs(x + dx[i], y + dy[i], d);
    }
}
 
int main(void)
{
    cin >> M;
 
    for (int i = 1; i <= M; i++)
    {
        for (int j = 1; j <= M; j++) scanf("%1d", &map[i][j]);
    }
 
    for (int i = 1; i <= M; i++)
    {
        for (int j = 1; j <= M; j++)
        {
            if (map[i][j] == 1 && check[i][j] == 0) { dfs(j, i, d); d++; }
            else continue;
        }
    }
     
    sort(num, num + d);
 
    printf("%d\n", d - 1);
 
    if (d == 1 && num[1] == 0) { return 0; }
    else for (int i = 1; i < d; i++) printf("%d\n", num[i]);
     
    return 0;
}