문제링크: https://www.acmicpc.net/problem/1389
1389번: 케빈 베이컨의 6단계 법칙
첫째 줄에 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)이 주어진다. 둘째 줄부터 M개의 줄에는 친구 관계가 주어진다. 친구 관계는 A와 B로 이루어져 있으며, A와 B가 친구라는 뜻이다. A와 B가 친구이면, B와 A도 친구이며, A와 B가 같은 경우는 없다. 친구 관계는 중복되어 들어올 수도 있으며, 친구가 한 명도 없는 사람은 없다. 또, 모든 사람은 친구 관계로 연결되어져 있다.
www.acmicpc.net
6다리면 건너면 세상사람들을 다 알 수 있다~ 이런 느낌의 문제였습니다.
당연히 탐색이라면 dfs, bfs를 먼저 생각하셔야 합니다. 문제 조건으로 유저의 수 N (2 ≤ N ≤ 100)과 친구 관계의 수 M (1 ≤ M ≤ 5,000)입니다. 비교적 큰 수이기 때문에 dfs보다는 bfs를 먼저 생각했습니다.
각각의 n번에서 최적탐색을 통해서 가장 빨리 도달하는 관계의 합을 더해주면 되는 방식이였습니다.
정답코드입니다. bfs코드이고 4ms 정도의 시간이 걸립니다. 풀면서도 살짝 긴가민가 했습니다.
왜냐하면 O(n*m*n*큐)이고 대략 50,000,000 이상의 반복연산을 하기때문입니다. 1억번에는 훨씬 못미치지만 반복을 재외한 큐이므로 큐자체도 100번은 반복하지 않을까하는 생각때문입니다.
다행히 문제는 통과했습니다. ( 1초에 1억번이라는게 정확한 연산은 아니기도 하고 큐에 대해서 제가 놓치고 있는 부분이 있기에 통과된것같습니다.)
#include <iostream>
#include <cstring>
using namespace std;
int n = 0, m = 0;
int arr[5001][2];
int visited[5001];
int result = 1000000000,result_index =-1;
int bfs(int num) {
int val = 0;
int que[5000];
for (int i = 1; i <= n; i++) {
if (num == i) continue;
memset(que, 0, 5000);
memset(visited, 0, 5001);
int started = 0, ended = 0;
que[ended++] = num;
visited[num] = 1;
while (ended != started) {
int a = que[started++];
if (a == i) {
val += visited[a] - 1;
break;
}
for (int j = 0; j < m; j++) {
if (arr[j][0] == a && !visited[arr[j][1]]) {
que[ended++] = arr[j][1];
visited[arr[j][1]] = visited[a] + 1;
}
else if (arr[j][1] == a && !visited[arr[j][0]]) {
que[ended++] = arr[j][0];
visited[arr[j][0]] = visited[a] + 1;
}
}
}
}
return val;
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++)
cin >> arr[i][0] >> arr[i][1];
for (int i = 1; i <= n; i++) { //1~n번까지의 경로를 탐색
int val = bfs(i);
if (result > val) result = val, result_index = i;
}
cout << result_index << endl;
}
근데 생각해보니 더욱 효율적인 방법이 있었습니다.
굳이 bfs문에서 n번 반복해줄 필요가 없었습니다...
어차피 while문이 한번다 돌고나면 visited엔 모든 인덱스별 최단경로값이 들어가있게 됩니다.
친구 관계는 중복되어 들어올 수도 있으며, 친구가 한 명도 없는 사람은 없다. 또, 모든 사람은 친구 관계로 연결되어져 있다.
이 문제조건 때문입니다.
수정코드입니다.
시간도 0ms로 줄었습니다.
#include <iostream>
#include <cstring>
using namespace std;
int n = 0, m = 0;
int arr[5001][2];
int visited[5001];
int result = 1000000000,result_index =-1;
int bfs(int num) {
int val = 0;
int que[5000];
memset(que, 0, 5000);
memset(visited, 0, 5001);
int started = 0, ended = 0;
que[ended++] = num;
visited[num] = 1;
while (ended != started) {
int a = que[started++];
for (int j = 0; j < m; j++) {
if (arr[j][0] == a && !visited[arr[j][1]]) {
que[ended++] = arr[j][1];
visited[arr[j][1]] = visited[a] + 1;
}
else if (arr[j][1] == a && !visited[arr[j][0]]) {
que[ended++] = arr[j][0];
visited[arr[j][0]] = visited[a] + 1;
}
}
}
for (int i = 1; i <= n; i++)
val += visited[i] - 1;
return val;
}
int main() {
cin >> n >> m;
for (int i = 0; i < m; i++)
cin >> arr[i][0] >> arr[i][1];
for (int i = 1; i <= n; i++) { //1~n번까지의 경로를 탐색
int val = bfs(i);
if (result > val) result = val, result_index = i;
}
cout << result_index << endl;
}
dfs코드입니다. 다른 분의 코드를 참고해서 만들었습니다. 216ms로 시간이 오래걸립니다. 어느 것이 더욱 좋다 이 것보다는 자기한테 편한코드로 ac를 받으면 되는거라고 생각합니다. dfs의 장점은 명료하고 직관적이라는 것입니다. 다음뻔에는 dfs로 풀어야하는 문제를 리뷰하겠습니다. 모두 화이팅 :)
#include <iostream>
#include <stdio.h>
#include <math.h>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
#define MAX 102
#define INF 987654321
using namespace std;
int n,m;
int a,b;
int ans,res,step;
int person;
bool check[MAX];
vector<int> v[MAX];
void dfs(int ind,int goal,int cnt){
if(ind == goal){
step = min(step,cnt);
return;
}
for(int i=0; i<v[ind].size(); i++){
if(!check[v[ind][i]]){
check[ind] = true;
dfs(v[ind][i],goal,cnt+1);
check[ind] = false;
}
}
}
int main(int argc, const char * argv[]) {
// cin,cout 속도향상
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
// 입력
cin >> n >> m;
for(int i=0; i<m; i++){
cin >> a >> b;
v[a].push_back(b);
v[b].push_back(a);
}
// 탐색
ans = INF;
for(int i=1; i<=n; i++){
memset(check, false, sizeof(check));
res = 0;
for(int j=1; j<=n; j++){
step = INF;
if(i==j) continue;
else{
dfs(i,j,0);
res += step;
}
}
// 최소인지 검사
if(ans > res){
ans = res;
person = i;
}else if(ans == res){
person = min(person, i);
}
}
cout << person << endl;
}'알고리즘 > BFS' 카테고리의 다른 글
| [백준] 2206-벽 부수고 이동하기(C++) (0) | 2020.04.03 |
|---|---|
| [백준] 8061-Bitmap (0) | 2020.03.26 |
| [백준] 9205-맥주 마시면서 걸어가기(C++) (0) | 2020.03.12 |
| [백준] 5014-스타트링크(C++) (1) | 2020.03.12 |
| [백준] 2589-보물섬(C++) (0) | 2020.03.08 |
