회의준비

문제 분석 및 풀이

설계 분석

• 간선의 목록이 주어졌을 때 이들을 그룹화하고 대표를 정하는 문제
  • Union - Find 연산을 통해서 그룹화
  • 대표 선정
    • 문제의 예시에서 1번이 대표면 3번은 3-2-1경로, 2번이 대표면 3-2 경로
    • 각 노드에서 가장 멀리 떨어진 노드까지의 거리가 가장 작은 것을 대표로
    • 플로이드 워셜을 통해 미리 거리를 계산
  $O(N^3)$

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <unordered_map>
#include <map>
#include <set>
#include <cmath>
using namespace std;

const int INF = 10e8;

vector<vector<int>> graph;
vector<int> parent;
map<int, vector<int>> group;

int N, M;

int Find(int x)
{
    if (parent[x] == x) return x;
    return parent[x] = Find(parent[x]);
}

void Union(int A, int B)
{
    A = Find(A);
    B = Find(B);

    if (A == B) return;
    parent[A] = B;
}


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

    cin >> N >> M;

    // 그래프 + 거리
    graph = vector<vector<int>>(N+1, vector<int>(N+1, INF));
    // 유니온 파인드를 위한 parent
    parent = vector<int>(N+1);

    // 초기에 자신의 부모는 자기 자신
    for (int i=1; i<=N; i++)
        parent[i] = i;
    
    // 그래프 초기화, Union
    for (int i=0; i<M; i++)
    {
        int u,v;
        cin >> u >> v;
        graph[u][v] = graph[v][u] = 1;
        Union(u,v);
    }

    // 그룹별로 map에 저장
    for (int i=1; i<=N; i++)
    {
        group[Find(i)].push_back(i);
    }

    // 플로이드 워셜
    for (int k=1; k<=N; k++)
    {
        for (int i=1; i<=N; i++)
        {
            for (int j=1; j<=N; j++)
            {
                if (graph[i][j] > graph[i][k] + graph[k][j])
                    graph[i][j] = graph[i][k] + graph[k][j];
            }
        }
    }

    // 정답 출력용 set
    set<int> ans;

    // 각 그룹별로 연산
    for (auto g : group)
    {
        auto key = g.first;
        auto& vec = g.second;

        int rep = -1;
        int best = INF;

        // 각 그룹의 한 노드에서 다른 노드까지의 거리중
        // 가장 긴 거리를 추출
        for (auto from : vec)
        {
            int max_dist = -1;
            for (auto to : vec)
            {
                if (from == to) continue;
                max_dist = max(max_dist, graph[from][to]);
            }

            // 가장 긴 거리중에서 가장 작은것을 가진 노드가 대표
            if (best > max_dist)
            {
                best = max_dist;
                rep = from;
            }
        }

        // 정답 배열에 삽입
        ans.insert(rep);
    }

    cout << ans.size() << "\n";
    
    for (auto& e : ans)
    {
        cout << e << endl;
    }

    return 0;
}