문제링크 : https://www.acmicpc.net/problem/1389
#include<bits/stdc++.h>
using namespace std;
int N, M;
// 이미 방문한 노드를 재방문 하지 않기 위한 배열
bool ch[101];
// 각 노드에서 다른 노드들로의 길이의 합을 저장한 배열
bool chVal[101];
// 친구 관계에 대한 정보를 저장한 배열
vector<int> a[101];
int main(){
ios_base::sync_with_stdio(false);
freopen("../input.txt","rt",stdin);
cin >> N >>M;
int ta, tb;
for(int i=1; i<=M; i++){
cin >> ta >> tb;
a[ta].push_back(tb);
a[tb].push_back(ta);
}
int res = 0;
int resSum = 2147000000;
for(int i=1; i<=N; i++){
// for문을 통해 모든 노드들을 순차적으로 한번씩 BFS를 한다.
memset(ch, false, sizeof(ch));
memset(chVal, false, sizeof(chVal));
queue<pair<int, int> >q;
ch[i] = true;
q.push(make_pair(i, 0));
int sum = 0;
while(!q.empty()){
int ret = q.front().first;
int val = q.front().second;
// 다른 노드로 가는 최단거리가 나올때마다 sum에 넣어준다.
// 단 이미 최단거리를 구할경우 그냥 패스한다.
if(!chVal[ret]){
chVal[ret] = true;
sum += val;
}
q.pop();
if(!ch[ret]) continue;
for(int i=0; i<a[ret].size(); i++){
if(!ch[a[ret][i]]){
ch[a[ret][i]] = true;
q.push(make_pair(a[ret][i], val+1));
}
}
}
if(sum < resSum){
res = i;
resSum = sum;
}
}
// cout << res << endl;
return 0;
}
문제만 케빈베이커 ~~~ 하면서 어렵게 만든거지 사실상 한 노드에서 다른노드들로 가는 최단거리들의 합을 구하는 문제이다. 문제들을 잘 해석할 줄 알아야한다.