백준 1389 케빈 베이컨의 6단계 법칙(Floyd Warshall)

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

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

#include <iostream>

using namespace std;

const int MAX = 100 + 1;
int graph[MAX][MAX];
int N, M;
int ans_value = 987654321;
int ans_order;

void floyd()
{
    for (int via = 1; via <= N; via++)
    {
        for (int from = 1; from <= N; from++)
        {
            if (graph[from][via] == 0)
                continue;
            for (int to = 1; to <= N; to++)
            {
                if (from == to || graph[via][to] == 0)
                    continue;
                if (graph[from][to] == 0 || graph[from][to] > graph[from][via] + graph[via][to])
                    graph[from][to] = graph[from][via] + graph[via][to];
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> N >> M;
    for (int i = 0; i < M; i++)
    {
        int first_friend, second_friend;
        cin >> first_friend >> second_friend;
        graph[first_friend][second_friend] = 1;
        graph[second_friend][first_friend] = 1;
    }
    floyd();
    /****************
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            cout<<graph[i][j]<<" ";
        }
        cout<<"\n";
    }
    *****************/

    for (int i = 1; i <= N; i++)
    {
        int sum = 0;
        for (int j = 1; j <= N; j++)
        {
            sum += graph[i][j];
        }
        if (ans_value > sum)
        {
            ans_value = sum;
            ans_order = i;
        }
    }
    cout << ans_order;
}

dfs 분류의 문제들만 풀다보니 dfs적으로만 접근했다...... 계속 고민하다가 포기하고 구글에 검색해서 플로이드 와샬 알고리즘으로 풀면 된다는 것을 알게 되었다.... 플로이드 와샬 알고리즘으로 풀면 된다는 것만 알면 쉽게 풀 수 있는 문제이다. (기본적인 플로이드 와샬 알고리즘 코드와 완전히 똑같기 때문에)

 

void floyd()
{
    for (int via = 1; via <= N; via++)
    {
        for (int from = 1; from <= N; from++)
        {
            if (graph[from][via] == 0) //from에서 via로 가지 못하는 경우
                continue;
            for (int to = 1; to <= N; to++)
            {
                if (from == to || graph[via][to] == 0) //자신에서 자신으로 가는 경우와 via에서 to로 갈 수 없는 경우
                    continue;
                if (graph[from][to] == 0 || graph[from][to] > graph[from][via] + graph[via][to]) //최소값을 graph 배열에!
                    graph[from][to] = graph[from][via] + graph[via][to];
            }
        }
    }
}

 

항상 어딘가를 거쳐서 가야 하는 문제들이 나오면, 플로이드 와샬 알고리즘을 가장 먼저 의심해보자.