[BOJ] 1389. 케빈 베이컨의 6단계 법칙

풀이

#include <iostream>
#include <vector>
#include <queue>
#include <string.h>

using namespace std;

typedef struct point{
	int usr;
	int d;
} point;

int N, M;
int kb_cnt[101];
int is_visit[101];
vector<int> v[101];
queue<point> q;
int kb_rst[101];

void find_kb();
void bfs(int start);
point make_point(int usr, int d);

int main(){
	cin >> N >> M;
	for(int i = 1; i <= M; i++){
		int usr1, usr2;
		cin >> usr1 >> usr2;
		v[usr1].push_back(usr2);
		v[usr2].push_back(usr1);
	}	
	for(int i = 1; i <= N; i++){
		memset(kb_cnt, 0, sizeof(kb_cnt));
		memset(is_visit, 0, sizeof(is_visit));
		bfs(i);
	}
	find_kb();
}

void find_kb(){
	int min_rst = kb_rst[1];
	int kb = 1;
	for(int i = 2; i <= N; i++){
		if(min_rst > kb_rst[i]){
			min_rst = kb_rst[i];
			kb = i;
		}
	}
	cout << kb << endl;
}

void bfs(int start){
	is_visit[start] = 1;
	kb_cnt[start] = 0;
	q.push(make_point(start, 0));
	
	while(!q.empty()){
		point p = q.front();
		q.pop();
		int usr = p.usr;
		int d = p.d;
		for(int i = 0; i < v[usr].size(); i++){
			int next_usr = v[usr][i];
			if(!is_visit[next_usr]){
				is_visit[next_usr] = 1;
				kb_cnt[next_usr] = d + 1;
				q.push(make_point(next_usr, d + 1));
			}
		}
	}
	
	int sum = 0;
	for(int i = 1; i <= N; i++){
		sum += kb_cnt[i];
	}
	kb_rst[start] = sum;
}

point make_point(int usr, int d){
	point p;
	p.usr = usr; p.d = d;
	return p;
}

queue, vector의 STL을 알아두면 좋을 거 같다.
queue<pair<int, int>> q; 를 정의할 경우 구조체를 만들지 않아도 된다.