[문제]
https://www.acmicpc.net/problem/1389
[풀이]
BFS로 분류되어 BFS로 풀었으나 Floyd-Warshall Algorithm을 이용하는 방법도 있다고 한다. 이게 더 쉬울 것 같은데 이렇게도 한 번 풀어봐야겠다..
bfs 코드를 그대로 이용하면 되는데, 연결된 다리의 누적합을 구해서 비교해야 하므로 connect 배열에 연결 다리 수를 저장하도록 했다.
[코드]
#include <iostream>
#include <queue>
#include <cstring>
using namespace::std;
int relation[101][101];
int connect[101];
int result[101];
bool visited[101];
int N, M; //유저의 수, 친구 관계의 수
void bfs(int v){
queue<int> q;
q.push(v);
visited[v] = true;
while(!q.empty()){
int u = q.front();
q.pop();
for(int i=1; i<=N; i++){
if(relation[u][i]==1 && visited[i]==false){
visited[i]=true;
q.push(i);
connect[i] = connect[u]+1;
}
}
}
}
int main() {
//케빈 베이컨 수가 가장 작은 사람 출력.
cin >> N >> M;
for(int i=0; i<M; i++){
int a, b;
cin >> a >> b;
relation[a][b] = 1;
relation[b][a] = 1;
}
for(int i=1; i<=N; i++){
bfs(i);
for(int j=1; j<=N; j++){
result[i] += connect[j];
}
memset(visited, false, sizeof(visited));
memset(connect, 0, sizeof(connect));
}
int min = result[1];
int min_person = 1;
for(int i=2; i<=N; i++){
if(result[i]<min) {
min = result[i];
min_person = i;
}
}
cout << min_person;
}
'알고리즘 공부 및 문제 풀이 > 백준(BOJ)' 카테고리의 다른 글
[boj] 백준 1303 전쟁 - 전투 - DFS (0) | 2022.02.05 |
---|---|
[boj] 백준 1342 행운의 문자열 (0) | 2022.02.04 |
[c++] 백준 1309 동물원 - 동적계획법 (0) | 2022.02.03 |
[c++] 백준 1263 시간 관리 - 그리디 (0) | 2022.01.31 |
[c++] 백준 1254 팰린드롬 만들기 - 투포인터 (0) | 2022.01.28 |