[BOJ] 2667. 단지번호맞추기

백준의 2667번 문제를 DFS를 사용하여 재귀로 풀어보았다.

 

#include <stdio.h>
#include <algorithm>
using namespace std;

#define MAX_SIZE 25

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

int n;
int group_id;
int groups[MAX_SIZE * MAX_SIZE];

bool visited[MAX_SIZE][MAX_SIZE];
int map[MAX_SIZE][MAX_SIZE];

void dfs_recursion(int x, int y) {
    visited[x][y] = true;
    groups[group_id]++;

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

        if (map[nx][ny] == 1 && visited[nx][ny] == false) {
            if (0 <= nx && nx < n && 0 <= ny && ny < n)
                dfs_recursion(nx, ny);
        }
    }
}

int main() {
    scanf("%d", &n);

    int i, j;

    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++)
            scanf("%1d", &map[i][j]);
    }

    for (i = 0; i < n; i++) {
        for (j = 0; j < n; j++) {
            if (map[i][j] == 1 && visited[i][j] == false) {
                group_id++;
                dfs_recursion(i, j);
            }
        }
    }

    sort(groups + 1, groups + 1 + group_id);

    printf("%d\n", group_id);
    for (i = 1; i <= group_id; i++)
        printf("%d\n", groups[i]);

    return 0;
}