1 문제

그래프 완전 탐색으로 분리된 단지 찾기

2 Idea

모든 위치를 탐색하며 1이 나온 경우 그 시점부터 DFS로 완전 탐색
DFS 시 visit을 업데이트

3 Code

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

/**
 * TestCase 1:
3
1 0 1
0 1 0
1 0 1
    -> 5
 * 
 */

#include <iostream>
#include <vector>
#include <algorithm> //sort

typedef struct{
    int i;
    int j;
} pos;

const std::vector<std::vector<int>> DIRECTION = {
    {1, 0},
    {-1, 0},
    {0, 1},
    {0, -1},
};

int gDfsAnswer = 0;

void DFS(const std::vector<std::vector<bool>>& graph, std::vector<std::vector<bool>>& visit, const int N, const pos current){
    visit[current.i][current.j] = true;
    ++gDfsAnswer;

    for (const auto& dir : DIRECTION){
        const pos next = {current.i+dir[0], current.j+dir[1]};

        if ((next.i >= N) || (next.j >= N) || (next.i < 0) || (next.j < 0)){
            //out of graph
            //  continue this loop

            continue;
        }
        if ((!visit[next.i][next.j]) && (graph[next.i][next.j])){
            DFS(graph, visit, N, next);
        }
    }
}

void printDangee(const std::vector<std::vector<bool>>& graph, const int N){
    std::vector<int> dangee;

    std::vector<std::vector<bool>> visit(N, std::vector<bool>(N, false));

    for (int i=0; i<N; ++i){
        for (int j=0; j<N; ++j){
            if ((!visit[i][j]) && graph[i][j]){
                DFS(graph, visit, N, {i, j});

                dangee.push_back(gDfsAnswer);
                gDfsAnswer = 0;
            }
        }
    }

    std::sort(dangee.begin(), dangee.end());

    std::cout << dangee.size() << std::endl;
    for (const auto& it : dangee){
        std::cout << it << std::endl;
    }

    return;
}
int main(){
    int N = 0;
    std::cin >> N;

    std::vector<std::vector<bool>> graph(N, std::vector<bool>(N, false));

    for (int i=0; i<N; ++i){
        std::string temp;
        std::cin >> temp;

        for (int j=0; j<N; ++j){
            if (temp[j] == '1'){
                graph[i][j] = true;
            }
        }
    }

    printDangee(graph, N);

    return 0;
}