[백준] 회의준비

정태호·2022년 11월 26일
0

회의에 참여하는 참석자들간의 관계가 간선정보로 주어지고 해당 관계를 가지는 사람들은 하나의 위원회로 구성되어야 한다.
그렇게 구성된 위원회의 구성원과 관계가 없는 참석자들은 다른 그룹을 생성하게 되고 이 그룹의 개수와 그룹내에서 연결된 참석자들과 가장 최단 거리로 연결되며, 각 참석자까지의 거리의 최대값이 가장 작은 참석자를 찾아야 하는 문제이다.

먼저 각 그룹정보를 추려내기 위해 유니온 파인드 알고리즘을 사용하여 각 참석자들이 같은 그룹에 속하는지를 알아 낼수 있도록 했다.
다음으로 플로이드 와샬 알고리즘을 이용하여 하나의 정점(참석자)가 도달할 수 있는 모든 정점의 최단 거리를 구했다.(이때 도달할 수 없는(다른 그룹) 참석자의 가중치는 0이 된다.)

다음 두 과정을 통해 각 그룹의 개수와 정보, 각 정점가 도달할 수 있는 최단 거리 정보를 알아 낼수 있다.
이제는 이 정보를 각 그룹을 기준으로 추려나가기만 하면 된다.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int N, M;
int dp[101]; // 그룹 정보를 담을 변수
int metrix[101][101];

struct S {
	int node;
	int cost;
};

S buf[101]{}; // 그룹번호와 위원장 정보를 담을 변수

int find(int n) {
	if (dp[n] == 0)
		return n;
	return dp[n] = find(dp[n]);
}

bool cmp(S& a, S& b) {
	return a.node < b.node;
}


int main() {
	cin >> N >> M;
	int a, b;
	for (int i = 0; i < M; i++) {
		cin >> a >> b;
		
		//그룹 정보 수집
		int A = find(a);
		int B = find(b);
		if (A != B) dp[A] = B;

		metrix[a][b] = 1;
		metrix[b][a] = 1;
	}

	//각 하나의 정점에서 모든 정점까지의 최단 거리를 계산
	for (int i = 1; i <= N; i++) {
		for (int k = 1; k <= N; k++) {
			for (int j = 1; j <= N; j++) {
				if (metrix[k][i] && metrix[i][j]) {//1이상으로 경로가 존재할 경우
					if (!metrix[k][j] || metrix[k][j] > metrix[k][i] + metrix[i][j]) { //경로가 갱신되지 않았거나 새로운 경로가 비용이 더 작을 경우
						metrix[k][j] = metrix[k][i] + metrix[i][j];
					}
				}
			}
		}
	}

	// 계산된 최단거리를 기준으로 속해있는 그룹의 위원장시 최대값 비용을 기준으로 정점 정보를 갱신
	for (int i = 1; i <= N; i++) {
		int cost = 1;
		for (int k = 1; k <= N; k++) {
			if (i != k && cost < metrix[i][k]) cost = metrix[i][k];
		}
		

		int group = find(i);

		if (buf[group].cost == 0 || buf[group].cost >  cost) {
			buf[group].cost = cost;
			buf[group].node = i;
		}
	}

	//그룹별 최소비용 정보를 벡터에 저장
	vector<S> result;
	for (int i = 1; i <= N; i++) {
		if (buf[i].cost != 0) result.push_back(buf[i]);
	}

	//정점의 숫자를 기준으로 정렬
	sort(result.begin(), result.end(), cmp);

	cout << result.size() << "\n";
	for (auto& res : result) {
		cout << res.node << "\n";
	}

}

0개의 댓글