[2610_스페셜 저지] 회의준비 - Floyd-Warshall ★★★☆ / 복습 ○

[ 문제 ] : https://www.acmicpc.net/problem/2610

2610번: 회의준비

---

[ 문제 접근 ]

 

- 처음에 나는 BFS로 붙어있는 사람들끼리 그룹을 만들어주고.

그룹마다 그룹장을 정하는데 인접한 노드의 개수가 가장 많은 사람이 그룹장을 맡아야 한다고 생각했다.

그래서 인접리스트로 표현한 adjacent[101] 의 size()가 가장 큰 노드를 찾아 그룹장을 시켜준 코드가 아래의 코드이다.

 

또한 문제에서도 나와 있듯이 2명 이상이 그룹장이 가능할때는 아무나 출력해야 했고, 나는 인접한 엣지의 개수가 같으면 누구든 그룹장이 될 수 있다고 생각했다.   == > 이 부분도 틀렸다. ( 아래는 그 반례이다. )

 

 

 

                      [ 문제에서 주어진 케이스 ]                                               [ 내 오판에 대한 반례 ]

---

[ 처음 코드 ]

 

 

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

using std::cout; using std::cin;
using std::vector;

int n, m;

vector<int> adjancent[101];
bool visited[101];
vector<int> team_members;
vector<int> team_leaders;

void bfs(int start) {
	std::queue<int> q;
	q.push(start);
	visited[start] = true;
	while (!q.empty()) {
		int cur = q.front();
		team_members.push_back(cur);
		q.pop();
		for (auto elem : adjancent[cur]) {
			if (!visited[elem]) {
				visited[elem] = true;
				q.push(elem);
			}
		}
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	cin >> n;
	cin >> m;
	int a, b;
	while (m--) {
		cin >> a >> b;
		adjancent[a].push_back(b);
		adjancent[b].push_back(a);
	}
	// bfs로 연결되지 않은 애들 갯수 세고
	int cnt = 0;
	for (int i = 1; i <= n; i++) {
		if (!visited[i]) {//아직 방문하지 않았으면 bfs 하고 cnt++
			cnt++;
			bfs(i);

			int leader_size = 0;
			int leader = 0;
			for (vector<int>::iterator itr = team_members.begin(); itr != team_members.end(); itr++) {
				if (adjancent[*itr].size() >= leader_size) {
					leader_size = adjancent[*itr].size();
					leader = *itr;
				}
			}
			team_leaders.push_back(leader);
			team_members.clear();
		}
	}

	cout << cnt << '\n';
	std::sort(team_leaders.begin(), team_leaders.end());
	for (auto elem : team_leaders) {
		cout << elem << '\n';
	}

	return 0;
}

---

[ Key Point ]

 

👉 우선 BFS 로 팀을 나누고 팀원을 구하는것 까지는 OK.

     But, 그 다음에 팀장을 구할때는 플로이드 와샬을 이용해서 구해야한다. 거리를 전부 계산해줘야한다.

 

👉 그래프 입력 받을때 플로이드 와샬이 가능하게끔 이중배열 d[i][j]를 초기화 해줘야한다.

 

---

 

[ 수정한 코드 ]

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>

using std::cout; using std::cin;
using std::vector; 

int N, M;
const int INF = 987654321;
bool visited[101];
vector<int> graph[101];
std::map<int,vector<int>> team_member;
vector<int> team_leaders;
int d[101][101];


void floyd() {
	for (int k = 1; k <= N; k++) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				d[i][j] = std::min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}
}

void bfs(int start,int idx) {
	std::queue<int> que;
	que.push(start);
	visited[start] = true;
	team_member[idx].push_back(start);
	while (!que.empty()) {
		int cur = que.front();
		que.pop();
		for (size_t i = 0; i < graph[cur].size(); i++) {
			int next = graph[cur][i];
			if (!visited[next]) {
				visited[next] = true;
				que.push(next);
				team_member[idx].push_back(next);
				
			}
		}
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	cin >> N >> M;

	// dp 초기화.
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (i == j)d[i][j] = 0;
			else {
				d[i][j] = INF;
			}
		}
	}
   // 입력 
	while (M--) {
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
		d[a][b] = 1;  // 연결 되있으면 cost = 1
		d[b][a] = 1;
	}
    // BFS로 팀 나누고, 팀 멤버 구하기.
	int team_cnt = 0; // 팀 cnt
	for (int i = 1; i <= N; i++) {
		if (!visited[i]) {
			bfs(i, ++team_cnt);
		}
	}
    
	floyd();

    // 대표 선정하기. ( map<int,pair<int,int>  team_member 에 int(팀 번호), vector(멤버 번호) 있다.)
	vector<std::pair<int,int>> candidates;
	
	for (size_t i = 1; i <= team_cnt; i++) {

		for (size_t j = 0; j < team_member[i].size(); j++) {
			int request_time = 0;
			int cur = team_member[i][j];

			for (size_t k = 0; k < team_member[i].size(); k++) {
				if (j == k)continue;
				int next = team_member[i][k];
				 request_time+= d[cur][next];
			}
			candidates.push_back({ request_time,cur });
		}
		std::pair<int, int> leader = *std::min_element(candidates.begin(), candidates.end());
		team_leaders.push_back(leader.second);
		candidates.clear();
	}
	

	// 출력하기
	cout << team_cnt << '\n';
	std::sort(team_leaders.begin(), team_leaders.end());
	for (auto elem : team_leaders) {
		cout << elem << '\n';
	}

	
	return 0;
}

---

[ Key Point ]

 

👉 나는 각각의 노드 쌍의 거리를 구해서 합한 다음에 그 값이 제일 작은 사람을 대표로 구했다.

  // 대표 선정하기. ( map<int,pair<int,int>  team_member 에 int(팀 번호), vector(멤버 번호) 있다.)
	vector<std::pair<int,int>> candidates;
	
	for (size_t i = 1; i <= team_cnt; i++) {

		for (size_t j = 0; j < team_member[i].size(); j++) {
			int request_time = 0;
			int cur = team_member[i][j];

			for (size_t k = 0; k < team_member[i].size(); k++) {
				if (j == k)continue;
				int next = team_member[i][k];
				 request_time+= d[cur][next];
			}
			candidates.push_back({ request_time,cur });
		}
		std::pair<int, int> leader = *std::min_element(candidates.begin(), candidates.end());
		team_leaders.push_back(leader.second);
		candidates.clear();
	}

근데 실패.!!

 

테스트 케이스도 통과하고, 반례 찾아서 넣어봐도 정답도 나오는데 뭐가 문젠지 알 수가 없었다.

 

그래서 결국 다른 분들의 정답을 봤는데 대표 구할때 max를 쓰길래 왜 저렇게 구하는거지 내가 모르는 뭔가가 있나?? 한참을 고민하고 고민하다 문제를 다시 한번 읽어봤는데..ㅎ

 

위원회에서 모든 참석자들의 의사 전달시간 중 최댓값이 최소가 되도록 대표를 정하는 프로그램을 작성하시오!!!!!!!!!!!

 

나는 완전 다른 문제를 풀고 있었다ㅋㅋㅋㅋ

 

 

 

---

 

[ 최종 코드 ]

 

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<map>

using std::cout; using std::cin;
using std::vector; 

int N, M;
const int INF = 987654321;
bool visited[101];
vector<int> graph[101];
std::map<int,vector<int>> team_member;
vector<int> team_leaders;
int d[101][101];


void floyd() {
	for (int k = 1; k <= N; k++) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				d[i][j] = std::min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}
}

void bfs(int start,int idx) {
	std::queue<int> que;
	que.push(start);
	visited[start] = true;
	team_member[idx].push_back(start);
	while (!que.empty()) {
		int cur = que.front();
		que.pop();
		for (int i = 0; i < graph[cur].size(); i++) {
			int next = graph[cur][i];
			if (!visited[next]) {
				visited[next] = true;
				que.push(next);
				team_member[idx].push_back(next);
				
			}
		}
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	cin.tie(nullptr); cout.tie(nullptr);
	cin >> N >> M;

	// dp 초기화.
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (i == j)d[i][j] = 0;
			else {
				d[i][j] = INF;
			}
		}
	}

	while (M--) {
		int a, b;
		cin >> a >> b;
		graph[a].push_back(b);
		graph[b].push_back(a);
		d[a][b] = 1;
		d[b][a] = 1;
	}
	int team_idx = 0; // 팀 넘버
	for (int i = 1; i <= N; i++) {
		if (!visited[i]) {
			bfs(i, ++team_idx);

		}
	}
	floyd();

	int leader = 0;
	// 대표 선정하기.  맵에 팀 번호, 멤버 번호 있다.
	for (size_t i = 1; i <= team_member.size(); i++) {
		int pivot = INF;
		for (int j = 0; j < team_member[i].size(); j++) {
			int max = 0;
			int cur = team_member[i][j];
			for (int k = 0; k < team_member[i].size(); k++) {
				if (j == k)continue;
				int next = team_member[i][k];
				 max = std::max(max, d[cur][next]);
			}
			if (max < pivot) {
				pivot = max;
				leader = cur;
			}
		}
		team_leaders.push_back(leader);
	}

	// 출력하기
	cout << team_idx << '\n';
	std::sort(team_leaders.begin(), team_leaders.end());
	for (auto elem : team_leaders) {
		cout << elem << '\n';
	}

	
	return 0;
}

 

 

---

[ 다른 사람 풀이 ]

 

ref :: https://blog.naver.com/PostView.naver?blogId=programmer18&logNo=221467951513

ref :: https://everenew.tistory.com/168