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

문제 링크입니다: https://www.acmicpc.net/problem/1389

플로이드-와샬 알고리즘을 사용하여 푸는 문제였습니다.

최소 베이컨 수를 구해야하기 때문에,

1. i와 j가 아직 모르는 경우 k를 통해 아는 경우 단계 수를 업데이트하고

2. i와 j가 서로 알더라도 k를 통해 알면 단계 수가 줄어들 경우에도 업데이트합니다.

이후에는 각 사람마다 베이컨 수를 계산하고 동등한 베이컨 수더라도 인덱스가 적은 사람을 출력하라고 했기 때문에 result>sum일 때만 업데이트해주면 됩니다!

#include <iostream>

#include <algorithm>

using namespace std;

 

const int INF = 987654321;

const int MAX = 100 + 1;

 

int N, M;

int graph[MAX][MAX];

 

//전형적인 플로이드 알고리즘

void floyd(void)

{

        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 (graph[i][k] && graph[k][j])

                                 {

                                          if (graph[i][j] == 0)

                                                  graph[i][j] = graph[i][k] + graph[k][j];

                                          //베이컨의 수가 적어야하므로

                                          else

                                                  graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j]);

                                 }

}

 

int main(void)

{

        cin >> N >> M;

 

        for (int i = 0; i < M; i++)

        {

                 int node1, node2;

                 cin >> node1 >> node2;

 

                 graph[node1][node2] = graph[node2][node1] = 1;

        }

 

        floyd();

 

        int result = INF;

        int person;

        for (int i = 1; i <= N; i++)

        {

                 int sum = 0;

                 for (int j = 1; j <= N; j++)

                         sum += graph[i][j];

                 if (result > sum) //최소 베이컨 수일 때

                 {

                         result = sum;

                         person = i; //해당 사람을 저장

                 }

        }

 

        cout << person << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~