[BOJ] - 2667. 단지번호붙이기

[URL]

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

2667번: 단지번호붙이기

[풀이 과정]

 

*단순 재귀DFS

 

1. map[][] == 1인 곳 vector v에 push

2. v만큼 for문 돌며 재귀 dfs()

3. 첫번째 단지 발견시 check[][]을 cnt (2)로 채워준다.

   두번째 단지 발견지 check[][]을 cnt+1(3)으로 채워준다.

 

4. check배열 검사하며 갯수 카운팅

5. cand[]배열에 넣고 sort

6. 오름차순 정렬 된 cand[]배열 출력

 

[소스 코드]

 

#include <stdio.h>
#include <algorithm>
using namespace std;
 
int N;        // 5이상 25이하
int map[26][26];
int check[26][26];
 
int dx[] = { 0, 0, -1, 1 };
int dy[] = { -1, 1, 0, 0 };
 
int cand[1000];
 
void DFS(int cx, int cy, int val) {
 
    check[cx][cy] = val;
 
    for (int k = 0; k < 4; k++)
    {
        int nx = cx + dx[k];
        int ny = cy + dy[k];
 
        if (nx >= 0 && ny >= 0 && nx < N && ny < N)
        {
            if (map[nx][ny] == 1 && check[nx][ny] == 0)
            {
                DFS(nx, ny, val);
            }
        }
    }
}
 
int main() {
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            scanf("%1d", &map[i][j]);
        }
    }
 
    int groupCnt = 0;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (map[i][j] == 1 && check[i][j] == 0)
            {
                groupCnt++;
                DFS(i, j, groupCnt);
            }
        }
    }
 
    for (int k = 1; k <= groupCnt; k++)
    {
        int tempSum = 0;
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                if (check[i][j] == k)
                {
                    tempSum++;
                }
            }
        }
        cand[k - 1] = tempSum;
    }
 
    sort(cand, cand + groupCnt);
    printf("%d\n", groupCnt);
    for (int k = 0; k < groupCnt; k++)
    {
        printf("%d\n", cand[k]);
    }
 
    return 0;
}