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

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

백준에서 보면 문제가 bfs로 분류되어 있다.
여러 가지 방법으로 풀 수 있겠지만.. 사실 처음 문제를 보자마자 들었던 해결 방법은 다익스트라로 접근하는 것이었다.

 배열이 아닌 큐를 통해서 한 정점에서 다른 정점들의 최단 거리를 구하는 방법으로 접근하고자 했다.


그런데......다익스트라 알고리즘 소스 코드가 기억이 안났다........
실제로 이 문제를 꼭 풀어야 하는 test 상황이라면 다익스트라 소스코드를 볼 수 없기 때문에 어떻게 할지 고민하다가 

플로이드 알고리즘을 생각하게 됐다.


생각해보니깐 어떤 정점이 아니라 모든 정점에 대해서 얼마나 걸리는지를 풀어야 하는 문제이기 때문에 플로이드 알고리즘을 적용할 수 있다. 

N이 100이하이기 때문에 O(N^3)을 하더라도 시간 안에 풀 수 있기 때문이다.

주의할 점은 3개의 for 문을 돌 때
첫 번째에 있는 for 문의 정점이 거쳐가는 정점
두 번째에 있는 for 문의 정점이 출발하는 정점
세 번째에 있는 for 문의 정점이 도착하는 정점
이 되어야 한다.


처음에 안쪽부터 차례대로
출발하는 정점, 도착하는 정점, 거쳐가는 정점 순서대로 for 문을 돌리다 보니 오류가 났다.


수학적으로 왜 이 순서대로 해야 하는지는 명확하게 모르기 때문에..
조금 더 플로이드를 찾아보고 공부해야겠다.



그리고 가장 중요한 다익스트라 알고리즘........하........
항상 안보면 까먹는 그래프 알고리즘.... 최단 경로 문제를 찾아서 풀어보고 다시 다익스트라를 이용하여 위의 문제를 풀어야 겠다. 


그리고 풀게 되면 2가지 방법으로 소스코드를 공유!!!

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
int max_value=0xfffffff;
 
int main() {
 
    int N,M;
    cin>>N>>M;
    
    vector<vector<int>> graph(N+1,vector<int>(N+1,0));
    vector<int> vec(N+1,0);
    
    int s,e;
    for(int i=1;i<=M;i++){
        scanf("%d %d",&s,&e);
        graph[s][e]=graph[e][s]=1;
    }
    
    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;
                
                if(graph[i][k]==0 || graph[k][j]==0)
                    continue;
                
                //i에서 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 sum=max_value; //가장 작은 단계
    int ans=0;
    
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            
            vec[i]+=graph[i][j];
        }
        
        if(sum>vec[i]){
            sum=vec[i];
            ans=i;
        }
    }
    
    cout<<ans<<endl;
    
    return 0;
}