반나누기

문제 분석 및 풀이

설계 분석

머리로만 생각하니 막막해서 적어보여 접근했다

처음에는 왼쪽처럼 하다가 예제를 생각하며 각 노드의 입장에서 반드시 같은 반이 되어야하는 목록을 만들었고, 그 목록을 통해서 그래프를 만들었더니 예제의 정답과 동일한 형태가 만들어졌다.

• 각 노드에 연결되지 않은 노드들의 관계를 그래프로 나타낸다 (여 그래프)
  • 인접 행렬을 꽉 채우고 입력 받을 때 지운다 (내 생각) (메모리 폭발)
    • 각 노드에서 BFS를 해서 각 그룹의 크기를 구한다.
  • BFS를 연결되지 않은 방향으로 진행 (구글링)
    • 인접행렬 순회가 아니라, 미방문 노드들을 순화하며 큐에 넣음
    • i번 노드를 시작으로 하는 BFS가 끝나면 i와 같은 그룹에 속하는 노드들이 나옴

일반적인 BFS가 아니라 시간복잡도는 조금 간당간당 하다고 생각하는데 테스트케이스가 빡빡하지 않은 듯.
유니온-파인드와 차수를 이용해서 더욱 최적화할 수 있다고...

• $O(N)$

풀이

#include <iostream>
#include <vector>
#include <algorithm>
#include <set>
#include <unordered_set>
#include <unordered_map>
#include <queue>
using namespace std;

int N,M;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;

    // 그래프 초기화
    vector<vector<int>> graph(N+1);

    for (int i = 0; i < M; i++)
    {
        int a,b;
        cin >> a >> b;

        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    //방문하지 않은 노드들의 목록을 만든다.
    set<int> unvisited;
    vector<int> groups;
    for(int i=1; i<=N; i++) unvisited.insert(i); 

    // 각 노드에 대해서 BFS
    // 각 노드의 인접 노드를 방문하면서 연결되지 않은 노드를 기록
    for(int i=1; i<=N; i++)
    {
        // i번 노드를 시작점으로
        if (unvisited.count(i) == 0) continue;
        
        //BFS 진행
        queue<int> q;
        q.push(i);
        unvisited.erase(i);
        int groupSize = 1;

        while(!q.empty())
        {
            int u = q.front();
            q.pop();

            // 현재 노드의 인접노드들
            set<int> adj(graph[u].begin(), graph[u].end());

            vector<int> temp;
            // 방문하지 않은 노드중 현재 노드와 연결되지 않은 노드 추가.
            for (auto v : unvisited)
            {
                if (adj.count(v) == 0)
                {
                    temp.push_back(v);
                }
            }

            // 위에서 찾은 노드들을 같은 그룹에 추가
            for (auto v : temp)
            {
                q.push(v);
                unvisited.erase(v);
                groupSize++;
            }
        }

        // 그룹 추가
        groups.push_back(groupSize);
    }

    sort(groups.begin(), groups.end());

    cout << groups.size() << "\n";
    for (auto v : groups)
    cout << v << " ";
    
    return 0;
}