[백준] 1389-케빈 베이컨의 6단계 법칙(C++)

문제링크: https://www.acmicpc.net/problem/1389

1389번: 케빈 베이컨의 6단계 법칙

 

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;
}