백준 2610 c++ "회의준비" -[PlusUltraCode]

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

2610번: 회의준비

[필자 사고]

 

이 문제는 기본은 플로이드 와샬 알고리즘을 사용하여 푸는 문제이다.

 

다른 문제와 달리 이문제의 특징은 같은 그룹으로 묶어줘야 한다는 것이다. 유니온 파인드가 떠올랐고 바로 실행에 옮겼다.

 

유니온 파인드를 사용할 때 주의할 점은 parent로 index접근이 아닌 항상 find로 index접근을 해야 된다는 점이다.

 

또한 이 문제의 조심할 포인트는 모든 인간과의 거리의 합의 최소가아닌 한 명의 최대 사거리중 가장 작은 값을 골라야 된다는 점이다.

 

필자 또한 이 부분에서 많은 애를 먹었다.

 

이 정도의 개념을 가지고 있으면 문제없이 풀 수 있다.

 

[소스 코드]

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int N, M;

typedef struct Node {
	int teamNumber;
	int minCount;
	int minNumber;
	
}Node;
bool cmp(Node a, Node b) {
	return a.minNumber <= b.minNumber;
}

vector<vector<int>> Arr;
vector<int> parent;
vector<Node> Team;

int find(int a) {
	if (a == parent[a]) {
		return a;
	}
	return parent[a] = find(parent[a]);
}
void Union(int a, int b) {
	a = find(a);
	b = find(b);
	
	if (a != b) {
		parent[max(a,b)] = min(a,b);
	}
}

bool checkSame(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b)return true;
	return false;

}
const int INF = 987654321;
void Input() {
	cin >> N >> M;
	Arr.resize(N + 1);
	parent.resize(N + 1);
	for (int i = 0; i <= N; i++) {
		Arr[i].resize(N + 1, INF);
		parent[i] = i;
	}
	for (int i = 0; i <M; i++) {
		int s, e;
		cin >> s >> e;
		Arr[s][e] = 1;
		Arr[e][s] = 1;
		if (checkSame(s, e) == false) {
			Union(s, e);
		}

	}
}

void Floyd_Warshall() {
	for (int k = 1; k <= N; k++) {
		for (int s = 1; s <= N; s++) {
			for (int e = 1; e <= N; e++) {
				if (s == e)continue;
				Arr[s][e] = min(Arr[s][e], Arr[s][k] + Arr[k][e]);
			}
		}
	}
}

void makeTeam() {
	
	
	for (int i = 1; i <= N; i++) {
		int a = find(i);
	}
	
	
	vector<bool> visited;
	visited.resize(N + 1, false);

	
	for (int i = 1; i <= N; i++) {
		if (visited[find(i)] == false) {
			Team.push_back({ find(i) ,INF,find(i) });
			visited[find(i)] = true;
		}
	}
}



int main(void) {
	Input();
	if (N == 1) {
		cout << 1<<"\n" << 1;
		return 0;
	}
	Floyd_Warshall();
	makeTeam();

	for (int i = 1; i <= N; i++) {
		int maxCount = -1;
		for (int k = 1; k <= N; k++) {
			if (Arr[i][k] != INF && Arr[i][k] != 0&&i!=k) {
				if (maxCount < Arr[i][k]) {
					maxCount = Arr[i][k];
				}

			}
		}
		
		for (int k = 0; k < Team.size(); k++) {
			if (parent[i] == Team[k].teamNumber) {
				if (Team[k].minCount > maxCount) {
					Team[k].minCount = maxCount;
					
					Team[k].minNumber = i;
				}
			}
		}
	}
	sort(Team.begin(), Team.end(),cmp);
	cout << Team.size() << '\n';
	for (int i = 0; i < Team.size(); i++) {
		cout << Team[i].minNumber << "\n";
	}

}