1389번

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

2달전에 처음 풀 때는 DFS를 이용해서 각각의 사람마다 DFS를 전부 돌렸었다.

그런데 이번에 다시 풀 때는 플로이드 워셜 알고리즘을 통해서 풀 수 있었다. DFS로 풀 때보다 시간이 훨씬 줄었다.

<정답 코드 - 플로이드 워셜>

#include<iostream>
 
using namespace std;
int D[101][101];
int ans[101];
const int INF = 987654321;
int main()
{
    for (int i = 0; i < 101; i++)
    {
        for (int j = 0; j < 101; j++)
        {
            D[i][j] = i == j ? 0 : INF;
        }
    }
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        D[a][b] = 1;
        D[b][a] = 1;
    }
 
    for (int k = 1; k <= n; k++)
    {
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= n; j++)
            {
                if (D[i][j] > D[i][k] + D[k][j])
                {
                    D[i][j] = D[i][k] + D[k][j];
                }
            }
        }
    }
 
    int smallest = INF;
    int p;
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= n; j++)
        {
            ans[i] += D[i][j];
        }
 
        if (ans[i] < smallest)
        {
            smallest = ans[i];
            p = i;
        }
    }
 
    cout << p << endl;
 
    
 
    return 0;
}

<정답 코드 - DFS >

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int N, M;
int ans = 2100000000;
vector<int> v[101];
int sum[101];
int minn = 2100000000;
bool check[101];
void dfs(int start,int goal,int len)
{
    if (start == goal)
    {
        minn = min(len, minn);
        return;
    }
    
 
    for (int i = 0; i < v[start].size(); i++)
    {
        if (check[v[start][i]] == false)
        {
            check[v[start][i]] = true;
            dfs(v[start][i], goal, len + 1);
            check[v[start][i]] = false;
        }
    }
 
    return;
}
int main()
{
    //freopen("input.txt", "r", stdin);
    cin >> N >> M;
    for (int i = 0; i < M; i++)
    {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
 
    for (int i = 1; i <= N; i++)
    {
        sum[i] = 0;
        check[i] = true;
        for (int j = 1; j <= N; j++)
        {
            minn = 2100000000;
            if (i != j)
            {
                dfs(i, j,0);
                sum[i] += minn;
            }
            
        }
        check[i] = false;
    }
 
    int mini;
    for (int i = 1; i <= N; i++)
    {
        if (ans > sum[i])
        {
            ans = sum[i];
            mini = i;
        }
    }
 
    cout << mini << endl;
    
    return 0;
}