[C++][백준 1389] 케빈 베이컨의 6단계 법칙(BFS, 플로이드 워셜)

https://www.acmicpc.net/problem/1389

문제를 읽어보면 모든 정점에서 모든 정점까지의 거리를 전부 구해야 하므로 플로이드 워셜 알고리즘을 쓰면 되는데, 우선은 BFS로 풀이해 보았다

 

풀이 1 (BFS)

평범한 BFS 알고리즘 기반이나, 몇 단계를 거쳐서 도달했는지 체크해야 하기 때문에 queue를 <int, int> pair로 만들어 주었다

처음 시작은 0단계로 시작하고, 단계를 거칠 때마다 pair의 first 부분에 +1씩 해서 계산해 준다

 

제출 코드 (BFS)

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<int> v[101];

int bfs(int start, int target, bool visited[101])
{
    queue<pair<int, int>> q;
    q.push(make_pair(0, start));
    visited[start] = true;

    int level = -1;
    while(!q.empty())
    {
        pair<int, int> cur = q.front();
        q.pop();
        
        if (target == cur.second)
        {
            level = cur.first;
            break;
        }

        for (int i = 0; i < v[cur.second].size(); i++)
        {
            if (!visited[v[cur.second][i]])
            {
                q.push(make_pair(cur.first + 1, v[cur.second][i]));
                visited[v[cur.second][i]] = true;
            }
        }
    }
    return level;
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m, minCount = 100000, minP = 0;
    cin >> n >> m;
    while(m--)
    {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }

    for (int i = 1; i <= n; i++) // 시작 포인트
    {
        int count = 0;
        for (int j = 1; j <= n; j++) // 각 번호까지의 단계 구하기
        {
            if (i == j) continue;
            bool visited[101] = {0};
            count += bfs(i, j, visited);
        }
        if (count < minCount)
        {
            minCount = count;
            minP = i;
        }
    }
    cout << minP;
}

 

풀이 2 (플로이드 워셜)

플로이드 워셜 알고리즘이란, a 점에서 b 점까지 가는 경로를 구하기 위해 사이에 k 점을 하나씩 넣어가며 최단경로를 찾는 알고리즘이다

    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

코드 중 이 부분이 가장 핵심적이라고 보면 된다

 

제출 코드 (플로이드 워셜)

#include <iostream>
using namespace std;

int dist[101][101];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    int n, m, minCount = 100000, minP = 0;
    cin >> n >> m;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            dist[i][j] = 100; // 최대 인원이 100이므로 최대 길이는 99, 따라서 100으로 초기화

    while (m--)
    {
        int a, b;
        cin >> a >> b;
        dist[a][b] = 1;
        dist[b][a] = 1;
    }

    for (int k = 1; k <= n; k++)
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= n; j++)
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);

    for (int i = 1; i <= n; i++)
    {
        int count = 0;
        for (int j = 1; j <= n; j++)
        {
            if (i == j) continue;
            count += dist[i][j];
        }
        if (count < minCount)
        {
            minCount = count;
            minP = i;
        }
    }

    cout << minP;
}