[BOJ알고리즘, C++]#1956_운동, 최단 경로, 플로이드, 플로이드 워셜

 

#1. 문제

1956번: 운동

 

---

 

#2. 풀이

 

1. 플로이드 워셜

[알고리즘]#2_길 찾기 알고리즘

 

[정의] : 플로이드-워셜 알고리즘은 음수 가중치를 포함하는 그래프의 "전체-쌍 최단 경로"를 구하는 알고리즘입니다. 만약, 그래프 내 순환 여부가 존재하면, dist [i][i](자기 자신을 출발점과 도착점으로 하는 사이클의 최단 경로 값)이 INT_MAX(초기값)이 아니라, 갱신된 다른 값으로 존재합니다. 따라서, 최단 경로 값을 갖는 사이클을 찾을 수 있습니다.

* 주의 : "벨만-포드"알고리즘은 단일-출발 혹은 단일-쌍 알고리즘으로, 주어진 출발 정점을 기준으로 그래프의 순환 여부를 검사하는 알고리즘입니다. 해당 문제는 최단 경로를 갖는 사이클을 찾기 위함이며, 시작 정점이 고정되어 있지 않아 벨만-포드 알고리즘은 해당 문제에서 적절하지 않습니다.

 

2. 다시 돌아오면, INT_MAX가 아니라 어떤 다른 값을 갖는다!

 

1. 2차원 vector 형식의 그래프를 구성합니다.
2. 플로이드-워셜 알고리즘을 수행하고, 각 정점을 순회하며 graph[i][i](정점 자신이 출발점인 동시에, 도착점인 최단 경로 값)이 최소가 되는 사이클을 찾으면 됩니다!

 

---

 

#3. 코드

 

// 문제 : 다익스트라 활용? 가장 짧은 싸이클을 찾는데 적절치 않다.
// 해결 : 플로이드-워셜 활용, dist[1][1]는 일반적으로 0이지만, '사이클'이 존재할 경우 dist[i][i]값이 갱신된다.

#include <iostream>
#include <vector>
#include <string>
#include <climits>
using namespace std;

int V, E;
vector<vector<int>> graph, dist;

void Floyd()
{
    for(int k=1; k <= V; ++k)
    {
        for(int u=1; u<=V; ++u)
        {
            for(int v=1; v<=V; ++v)
            {
                if(dist[u][k] != INT_MAX
                  && dist[k][v] != INT_MAX
                  && (dist[u][v] == INT_MAX || dist[u][v] > dist[u][k] + dist[k][v]))
                {
                    dist[u][v] = dist[u][k] + dist[k][v];
                }
            }
        }
    }
    
    int res = INT_MAX;
    for(int i=1; i<=V; ++i)
        res = min(res, dist[i][i]);
    
    if(res == INT_MAX) cout << -1;
    else cout << res;
    
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> V >> E;
    
    dist.resize(V+1, vector<int>(V+1, INT_MAX));
    
    while(E--)
    {
        int u, v, w;
        cin >> u >> v >> w;
        
        dist[u][v] = w;
    }
    
    Floyd();
    
    return 0;
}

 

---