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

백준의 케빈베이컨의 6단계 법칙(1389) 문제이다.

( 문제 바로가기 )

[ 문제설명 ]

- 모든 사람들은 최대 6단계 이내에 연결할 수 있다는 가정하에, 전체 유저의 수와 친구 관계의 수를 입력받고

   친구 관계를 입력으로 받는다.

- 친구 관계를 입력 받았을 때, 모든 사람들은 모두와 연결될 수 있는데, 이 때 가장 최소의 관계로 연결될 수 있는 사람의

  번호를 출력하면 된다.

- 사실 문제가 이렇게 설명하기 좀 까다롭다. 문제를 읽어보고 오자.

[ 문제풀이 ]

1. 이런 문제 같은 풀이는 플로이드워샬 알고리즘(Floyd-Warshall Algorithm)이 가장 좋다. 이런 문제 라는 것이 의미하는 것

   은.. 예를들어서 A와B는 친구이다. B와C는 친구이다. C와 D는 친구이다. A와D는 몇 다리 건너 D와 친구인가?

   이런 식으로 출발점에서 중간 지점을 거쳐, 도착점에 갈 수 있는 최소의 방법을 구하는 문제같은 것에는 플로이드 워샬

   알고리즘이 가장 좋다.

2. 하지만, 백준에는 BFS/DFS 분야로 문제가 올라와 있이므로, 본인은 플로이드워샬과 BFS/DFS 2가지 방법 모두 풀어보았

   다.

3. 먼저 플로이드워샬 알고리즘 풀이법이다.

   플로이드워샬 알고리즘의 가장 기본적인 틀은 3중 반복문이다. 여기서 가장 바깥쪽 반복문이 중간점 역할을 하며

   중간쪽 반복문이 시작점, 가장 안쪽 반복문이 도착점 역할을 한다.

  

for (int k = 1; k <= N; k++)
    {
        for (int i = 1; i <= N; i++)
        {
            for (int j = 1; j <= N; j++)
            {
                if (i == j) continue;
                else if (MAP[i][k] != 0 && MAP[k][j] != 0)
                {
                    if (MAP[i][j] == 0) MAP[i][j] = MAP[i][k] + MAP[k][j];
                    else MAP[i][j] = Min(MAP[i][j], MAP[i][k] + MAP[k][j]);
                }
            }
        }
    }

    보통 이런식으로 구현을 한다. 반복문 안에 있는 내용을 살펴보면, MAP[i][k]와 MAP[k][j]의 관계를 비교하는 조건문이

    하나있고, 그 조건문 안에서 값을 갱신해주는 구문이 있음을 확인할 수 있다.

    위에서 말한 것처럼, 위의 코드에서 k는 중간점, i는 시작점, j는 도착점 역할을 하는 변수들이며

    i와 k가 연결되어 있고, k와 j가 연결되어 있다면 값을 비교해서 가장 최단거리로 갱신시켜주는 방식이다.    

  4. 다음은 BFS/DFS 풀이법이다. 본인은 BFS로 풀이하였는데, 생각보다 간단하게 구현할 수 있다.

     BFS안에서는, 시작점을 기준으로 모든 정점을 비교하면서, 시작점과 연결되어있으면서도 아직 방문하지 않은 점을

     계속해서 Queue에 넣어주면서 BFS를 반복시켜 주면 된다.

     여기서 생각을 하나 해야할 것이, 문제가 가장 적은 단계로 모든 사람들과 연결될 수 있는 사람을 구하는 것이다. 따라서,

     값을 계속해서 갱신할 수 있는 배열을 하나 사용하였다. Connect[] 라는 1차원 배열인데, 이 배열은 시작점으로 부터의

     거쳐지는 다리의 수를 계속해서 더해가는 것이다.

     예를 들어서, A와B가 친구, B와 C가 친구이면, Connect[B] = 1, Connect[C] = Connect[B] + 1 이런식으로, 

     물론 실제로는 저 배열 인덱스가 들어가는 부분에 영어가 들어갈 수는 없지만 편의상 이렇게 설명하겠다.

     이런식으로 A로부터의 모든 관계를 다 구한후에, A의 총 다리의 수를 더해주는 과정만 있으면 된다.

     자세한건, 코드를 보면 이해가 쉬울 것이다. 총 다리의 수를 저장하는 변수는 Result_BFS[]라는 배열을 사용하였다.

[ 소스코드 ]

< 한 코드안에, 2개의 풀이법이 모두 들어가 있으니, 잘 구분할 것 ! >

#include<iostream>
#include<cstring>
#include<queue>
 
#define endl "\n"
#define MAX 100
using namespace std;
 
int N, M;
int MAP[MAX][MAX];
int Connect[MAX];
int Result_BFS[MAX];
bool Visit[MAX];
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        MAP[a][b] = 1;
        MAP[b][a] = 1;
    }
}
 
void Solution()
{
    for (int k = 1; k <= N; k++)
    {
        for (int i = 1; i <= N; i++)
        {
            for (int j = 1; j <= N; j++)
            {
                if (i == j) continue;
                else if (MAP[i][k] != 0 && MAP[k][j] != 0)
                {
                    if (MAP[i][j] == 0) MAP[i][j] = MAP[i][k] + MAP[k][j];
                    else MAP[i][j] = Min(MAP[i][j], MAP[i][k] + MAP[k][j]);
                }
            }
        }
    }
}
 
int MinPerson()
{
    int Result = 999999;
    int Person = 1;
    for (int i = 1; i <= N; i++)
    {
        int Tmp_Result = 0;
        for (int j = 1; j <= N; j++)
        {
            Tmp_Result = Tmp_Result + MAP[i][j];
        }
 
        if (Result > Tmp_Result)
        {
            Result = Tmp_Result;
            Person = i;
        }
    }
    return Person;
}
 
void Solve_FloydWarShall()
{
    Input();
    Solution();
    int Answer = MinPerson();
 
    cout << Answer << endl;
}
 
void BFS(int a)
{
    queue<int> Q;
    Q.push(a);
    Visit[a] = true;
 
    while (Q.empty() == 0)
    {
        int x = Q.front();
        Q.pop();
 
        for (int i = 1; i <= N; i++)
        {
            if (MAP[x][i] == 1 && Visit[i] == false)
            {
                Visit[i] = true;
                Q.push(i);
                Connect[i] = Connect[x] + 1;
            }
        }
    }
}
 
int MinPerson2()
{
    int Min = Result_BFS[1];
    int Min_Person = 1;
    for (int i = 2; i <= N; i++)
    {
        if (Min > Result_BFS[i])
        {
            Min = Result_BFS[i];
            Min_Person = i;
        }
    }
    return Min_Person;
}
 
void Solution2()
{
    for (int i = 1; i <= N; i++)
    {
        BFS(i);
        for (int j = 1; j <= N; j++)
        {
            Result_BFS[i] = Result_BFS[i] + Connect[j];
        }
        memset(Visit, false, sizeof(Visit));
        memset(Connect, 0, sizeof(Connect));
    }
 
    int Ans = MinPerson2();
    cout << Ans << endl;
}
 
void Solve_BFSDFS()
{
    Input();
    Solution2();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
//    freopen("Input.txt", "r", stdin);
    Solve_FloydWarShall();
    Solve_BFSDFS();
 
    return 0;
}