[백준][C++] 1956 운동

www.acmicpc.net/problem/1956

1956번: 운동

 

 

 

알고리즘 종류

    - 플로이드 와샬

 

 

 

사고 과정

    1. 2차원 배열에 INF로 초기화한다.

    2. 플로이드 와샬로 값을 비교하면서 갱신한다.

    3. [v][v] 값들 중에서 최소 값을 출력한다. 경로가 없으면 -1을 출력한다.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#define INF 987654321
 
using namespace std;
 
int v, e;
int mat[401][401];
 
 
void FW(){
    
    for(int k=1; k<=v; k++){
        for(int i=1; i<=v; i++){
            for(int j=1; j<=v; j++){
                mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j]);
            }
        }
    }
}
 
int main(void){
    
    cin >> v >> e;
    
    for(int i=1; i<=v; i++){
        for(int j=1; j<=v; j++){
            mat[i][j] = INF;
        }
    }
    
    int a, b, c;
    for(int i=0; i<e; i++){
        cin >> a >> b >> c;
        mat[a][b] = c;
    }
    
    FW();
    
    int answer = 987654321;
    for(int i=1; i<=v; i++){
        if(mat[i][i] < answer) answer = mat[i][i];
    }
    if(answer >= INF) cout << -1;
    else cout << answer << endl;
    
}

 

 

 

시행착오

    - 처음에 MST를 생각했다. 다익스트라에서 서로 다른 두 노드의 부모가 다르면 사이클이 된다는 특징을 살려보려고 했다. 그런데, 이렇게 사이클이 발견되었을 때, 명확이 어떤 간선들이 사이클에 포함되는지 알아내는 것이 힘들다고 생각했다. 

    - 생각해보니, 1->1, 2->2, 3->3, ..., v->v 경로 중에서 가장 최소인 것을 찾으면 되는 것이었다. 이렇게 모든 노드들이 최소 경로를 갖게하는 알고리즘은 플로이드 와샬이다.