백준 2660번 - 회장뽑기 (C++)

 

2660번: 회장뽑기

 

BFS로 푸는 방법과 플로이드-워셜 알고리즘으로 푸는 방법 두가지가 있는데 플로이드-워셜로 먼저 풀고 BFS로 한번 더 풀어봤다.

 

1. 플로이드-워셜

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

using namespace std;
const int INF = 100;

int main() {
	int member;
	int m1, m2;
	cin >> member;

	vector<vector<int>> inti(member+1,vector<int>(member+1,INF));
	
	while (true) {
		cin >> m1 >> m2;
		if (m1 == -1 && m2 == -1) {
			break;
		}
		inti[m1][m2] = 1;
		inti[m2][m1] = 1;
	}
	for (int i = 1; i <= member; i++) {
		inti[i][i] = 0;
	}

	for (int k = 1; k <= member; k++) {
		for (int i = 1; i <= member; i++) {
			for (int j = 1; j <= member; j++) {
				inti[i][j] = min(inti[i][j], inti[i][k] + inti[k][j]);
			}
		}
	}

	vector<int> score(member+1);

	for (int i = 1; i <= member; i++) {
		score[i] = *max_element(inti[i].begin()+1, inti[i].end());
	}

	int cand_score = *min_element(score.begin()+1,score.end());
	int cand_cnt = 0;
	vector<int> cand;
	for (int i = 1; i <= member; i++) {
		if (cand_score == score[i]) {
			cand.push_back(i);
			cand_cnt++;
		}
	}

	cout << cand_score << ' ' << cand_cnt << endl;
	for (int i : cand) {
		cout << i << ' ';
	}
}

1. 입력을 받아 인접행렬에 각각의 거리를 표시. 처음엔 입력으로 들어온 값들의 거리는 1, 본인의 거리(행과 열이 같은 경우)는 0, 바로 연결되지 않으면 INF로 표시함

2. 플로이드-워셜 알고리즘으로 각 노드 간 최소거리 구하기

3. 각 행에서 가장 큰 값이 그 회원의 점수. 각 회원들의 점수를 벡터에 저장

4. score벡터에서 가장 작은 값이 후보의 점수

 

2. BFS

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

using namespace std;

int bfs(vector<vector<int>> list, int member, int start) {
	queue<int> Q;
	vector<int> dist(member + 1, -1);

	Q.push(start);
	int maxdis = 0;

	dist[start] = maxdis;
	
	while(!Q.empty()) {
		int key = Q.front();
		maxdis = dist[key];
		for (int i : list[key]) {
			if (dist[i] >= 0)	continue;
			Q.push(i);
			dist[i] = maxdis+1;
		}

		Q.pop();
	}
	return maxdis;
}

int main() {
	int member;
	int m1, m2;
	cin >> member;

	vector<vector<int>> inti(member + 1);

	while (true) {
		cin >> m1 >> m2;
		if (m1 == -1 && m2 == -1)
			break;
		inti[m1].push_back(m2);
		inti[m2].push_back(m1);
	}

	vector<int> score(member + 1);
	for (int i = 1; i < member + 1; i++) {
		score[i] = bfs(inti, member, i);
	}

	int cand_score = *min_element(score.begin() + 1, score.end());
	vector<int> cand;
	int cand_cnt = 0;
	for (int i = 1; i <= member; i++) {
		if (score[i] == cand_score) {
			cand.push_back(i);
			cand_cnt++;
		}
	}

	cout << cand_score << ' ' << cand_cnt << endl;
	for (int i : cand) {
		cout << i << ' ';
	}
	
}

1. 인접리스트에 입력값 저장

2. bfs를 이용해 가장 먼 노드까지의 거리를 구한 후 해당 값 리턴

3. 값들을 score벡터에 저장

4. score벡터에 가장 작은 값이 후보의 점수