[백준/C,C++] 1389번: 케빈 베이컨의 6단계 법칙

www.acmicpc.net/problem/1389

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

풀이

각 유저를 출발 노드로 모든 노드를 방문할 때까지 BFS를 실행한 뒤,

 

모든 노드를 방문했을 때의 깊이(depth)를 더한 값이 가장 작은 노드를 출력하면 됩니다.

 

모든 정점에서 모든 정점을 방문해야 할 때, 플로이드 와샬이라는 알고리즘을 사용할 수 있던데

 

자세한 내용은 ko.wikipedia.org/wiki/%ED%94%8C%EB%A1%9C%EC%9D%B4%EB%93%9C-%EC%9B%8C%EC%85%9C_%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

플로이드-워셜 알고리즘 - 위키백과, 우리 모두의 백과사전

위키백과를 확인해보시면 될 것 같습니다.

 

아래는 플로이드 와샬 알고리즘을 사용해 구현해본 코드입니다.

 

#include<iostream>

using namespace std;

const int MAX = 101;

int n, m;
int net[MAX][MAX];

int main(void)
{
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        net[a][b] = 1;
        net[b][a] = 1;
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            if (i != j && net[i][j] != 1) {
                net[i][j] = 10000000;
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            for (int k = 1; k <= n; k++) {
                if (net[j][i] + net[i][k] < net[j][k]) {
                    net[j][k] = net[j][i] + net[i][k];
                }

            }
        }
    }

    int val = 10000000;
    int res;
    for (int i = 1; i <= n; i++) {
        int tmp = 0;
        for (int j = 1; j <= n; j++) {
            tmp += net[i][j];
        }
        if (tmp < val) {
            val = tmp;
            res = i;
        }
    }

    cout << res;

    return 0;
}

 

아래는 BFS를 사용해 구현한 코드입니다.

 

그래프의 기초에 대해 공부 중이기 때문에 BFS로 구현하는 걸 목표로 하고

 

플로이드 와샬 알고리즘은 이런 게 있구나 정도로 구현만 해보았습니다.

 

#include<iostream>
#include<queue>
#include<cstring>

using namespace std;

const int MAX = 101;

int n, m;
int net[MAX][MAX];
bool visited[MAX];
int cnt[MAX];
int tmp = MAX;
queue<int> q;

void visit(int num)
{
    q.push(num);
    visited[num] = true;
}

bool BFS(int num)
{
    visit(num);
    while (!q.empty()) {
        int user = q.front();
        q.pop();
        for (int i = 1; i <= n; i++) {
            if (!visited[i] && net[user][i]) {
                cnt[i] = cnt[user] + 1;
                visit(i);
            }
        }
    }
    int sum = 0;
    for (int i = 1; i <= n; i++) sum += cnt[i];
    if (sum < tmp) {
        tmp = sum;
        return true;
    }
    else return false;
}

int main(void)
{
    cin >> n >> m;

    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        net[a][b] = 1;
        net[b][a] = 1;
    }

    int res;
    for (int i = 1; i <= n; i++) {
        if (BFS(i)) res = i;
        memset(visited, false, sizeof(visited));
        memset(cnt, 0, sizeof(cnt));
    }

    cout << res;

    return 0;
}

반례

Input

5 7
1 2
1 3
2 3
2 4
3 4
3 5
4 5

Output

3

 

Input

6 8
1 3
5 2
6 3
4 5
3 1
4 1
5 4
2 6

Output

1