[백준 2610] 회의준비 C++

#include <bits/stdc++.h>
#define FASTIO ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
#define INF 987654321
using namespace std;

int dist[101][101];
int visited[101];
int leader[101];
int num = 0;
int V, E;

int main() {
	FASTIO;
	cin >> V >> E;

	//초기값 설정
	for (int i = 1; i <= V; i++) {
		for (int j = 1; j <= V; j++) dist[i][j] = INF;
	}

	for (int i = 1; i <= V; i++)dist[i][i] = 0;

	for (int i = 0; i < E; i++) {
		int a, b; cin >> a >> b;
		dist[a][b] = 1;
		dist[b][a] = 1;
	}
	//플로이드 실행 
	for (int k = 1; k <= V; k++) {
		//k를 경유해서 감
		for (int i = 1; i <= V; i++) {
			for (int j = 1; j <= V; j++) {
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
			}
		}
	}
	
	//문제 풀이
	int tmp[101];
	int min_dis=9999;
	int tmp_max = 0;
	int tmp_leader = 0;
	int leader[101];
	for (int i = 1; i <= 100; i++) {
		visited[i] = 0;
	}

	for (int i = 1; i <= V; i++) {
		//tmp초기화 하고 시작 
		
		for (int k = 1; k <= V; k++) {
			tmp[k] = 0;
		}
		if (visited[i] == 1) {
			//cout << " contincue" <<  i << "\n";
			continue;
		}
		//cout<<"step = " << i << "\n";
		// i 번째 vertex 와 연결되어 있는 vertex를 tmp를 이용해 모두 찾기.
		visited[i] = 1;
		tmp[i] = 1;
		for (int j = 1; j <= V; j++) {
			if (dist[i][j] != INF  && visited[j] ==0) {
				//cout << "j =" << j << "\n";
				tmp[j] = 1;
				visited[j] = 1;
			}
		}
		// i번째 vertex와 연결되어 있는 vertex중 leader를 찾음 
		for (int k = 1; k <= V; k++) {
			if (tmp[k] == 1) {
				//cout << "tmp[k] == 1 k =" << k << "\n";
				for (int j = 1; j <= V; j++) {
					if (dist[k][j] != INF && tmp_max < dist[k][j])
						tmp_max = dist[k][j];
				}
				if (tmp_max < min_dis) {
					min_dis = tmp_max;
					tmp_leader = k;
					//cout << "tmp_leader is = " << k << "\n";
				}
			}
			tmp_max = 0;
		}
		min_dis = 9999;
		leader[num] = tmp_leader;
		num++;
	
	}
	cout<< num<<"\n";
	sort(leader, leader + num);
	for (int itor =0; itor < num; itor++)
		cout << leader[itor] << "\n";
}

회의의 총 인원이 최대 100명이다. 따라서 플로이드 워셜 알고리즘으로 풀었다. 

 

두가지의 문제가 있었는데, 첫번째 문제는  "최대 거리"를 생각하지 않은 점이다.

리더는 모두와의 거리의 합산이 가장 작은 사람일거라 생각했는데, 

문제를 다시 보니 가장 먼 팀원간의 거리가 , 가장 작은 사람을 리더로 뽑는 거였다.

이것에 대한 검증 예제는 다음과 같다.

 

input

9

8

1 2

2 3

3 4

4 5

4 6

4 7

4 8

4 9

output 

1

3

 

여기서 1 4 가 나온다면 , leader를 뽑는 법을 잘못 생각하고 있는 것이다. 

 

두번째 오류는 , 리더의 선출이 첫번째 vertex 부터 시작되므로 자동으로 오름차순으로 출력될 것이라고 생각해서 발생했다.

아래의 test case로 체크할 수 있다.

 

input

5
2
1 4
4 5

 

output

3
4
2
3