[Baekjoon,1956] 운동

모든 정점을 찾으며 자기 자신으로 돌아오는 경로가 존재하는 정점 중에서 경로의 최소값을 찾아야 한다. 여기서 플로이드 알고리즘을 활용할 수 있다.

플로이드 알고리즘

플로이드 알고리즘을 간단히 설명하면 정점 $u$에서 $v$로 가는 경로가 경유점 $k$를 이용한 것이 더 빠른가 아닌가를 이용하여 모든 정점 쌍에 대해 최단거리를 구하는 것이다. 이때 핵심은 경유점 목록을 하나씩 추가하며 갱신해 나아가면 별다른 배열 선언 없이 그래프의 인접 행렬 $adj[][]$만을 가지고 값을 생성할 수 있다는 것이다. 왜냐하면 시작점부터 $k-1$번 정점까지를 경유점으로 이용하여 $u$에서 $k$로 가는 최단 경로나 여기서 $k$ 정점을 경유점 집합에 추가하나 같기 때문이다.
이는 “알고리즘 문제 해결 전략”에 좋은 비유가 있다.

” ‘지하철역과 63빌딩을 들러 63빌딩에 가는 최단 경로’와 ‘지하철역과 63빌딩을 들러 63빌딩에 가는 최단 경로’가 똑같은 것과 마찬가지죠! “

---

문제에 적용

그렇다면 어떻게 문제에 적용할까? 방법은 자기 자신으로 돌아와야 하니 초기에 자기 자신으로 가는 경로도 INF로 설정 하는 것이다. 이렇게 하면 자기 자신으로 돌아오는 경로가 없을 시 INF로 그대로 있을 것이며 모든 정점에 대해 자기 자신으로 돌아오는 경로의 값이 저장 될 것이다.
이후 모든 정점을 돌며 가장 작은 값을 찾으면 된다.

---

구현

이를 구현한 코드를 아래에서 볼 수 있다.

#include <iostream>
using namespace std;

const int INF=987654321;
const int MAX_V=400;

int V;
int adj[MAX_V][MAX_V];

void floyd()
{
    for(int k=0;k<V;++k)
        for(int i=0;i<V;++i)
            for(int j=0;j<V;++j)
                adj[i][j]=min(adj[i][j],adj[i][k]+adj[k][j]);
}

int main()
{
    int e;
    cin>>V>>e;
    // 자기 자신으로 가는 간선도 INF로 초기화
    for(int i=0;i<V;++i)
        for(int j=0;j<V;++j)
            adj[i][j]=INF;
    
    for(int i=0;i<e;++i)
    {
        int a,b,c;
        cin>>a>>b>>c;
        --a;--b;
        adj[a][b]=c;
    }
    
    floyd();
    
    int ret=INF;
    for(int i=0;i<V;++i)
        ret=min(ret,adj[i][i]);
    
    if(ret==INF)
        cout<<-1<<endl;
    else
        cout<<ret<<endl;
    
    return 0;
}