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

문제

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

1956번: 운동

 

풀이 과정

플로이드-워셜(floyd-warshall) 알고리즘을 이용한다. 해당 알고리즘은 2차원 배열을 이용하여 두 노드를 잇는 최단거리를 구하는 알고리즘이다. 이때 노드의 최단 거리를 구할 때 자기 자신의 노드는 0으로 설정하는데, 이 부분만 수정한다면 위의 문제를 해결할 수 있다.

 

아래의 그림은 플로이드 워셜 알고리즘이 적용되기 전, 후의 상태를 나타낸다.

출처 : Foundations of Algorithms 5th edition

 

플로이드 워셜 알고리즘의 핵심은 두 노드를 잇는 최단거리를 계속 기록하면서 업데이트하는 것에 있다.

i와 j를 잇는 거리에 대해 k를 경유하여 가는 것이 더 짧다면 이전에 기록되었던 길이 대신 더 짧은 길을 기록하는 것을 의미한다.

이전에 기록되었던 최단 거리들이 어떤 경로로 선택되었던 것인지는 상관없고 더 짧기만 하다면 짧은 거리를 배열에 기록하는 방식이다.

 

 

백준 1956번 운동 문제는 시작 지점으로 다시 돌아오는 cycle의 거리를 알고 싶다.

따라서 자기 자신까지의 최단 거리를 0으로 설정하지 않고 무한대로 설정한 뒤 플로이드-워셜 알고리즘을 적용한다면 자기 자신에게서 출발해서 다시 자기 자신으로 돌아오는 거리를 배열에 기록할 수 있다. 이후 dist [i][i]에 기록된 사이클의 최단 길이를 기록하며 탐색한다.

 

이때 최단 길이가 무한대로 설정한 값 그대로라면, 주어진 조건에는 사이클이 존재지 않는 것을 의미하며 -1을 출력한다. 그렇지 않으면 기록된 최단 거리를 출력한다.

 

 

소스 코드

#include <iostream>
#include <algorithm>
#include <cstring>
#define INF 9999999

using namespace std;
const int max_v = 401;
int dist[max_v][max_v];

int v,e;

void print_ary(int ary[][max_v]){
    for(int i=1;i<=v;i++){
        for(int j=1;j<=v;j++){
            cout << ary[i][j] << " ";
        }
        cout << "\n";
    }
}


int main(){
    //Input
    cin >> v >> e;
    for(int i=1;i<=v;i++){
        for(int j=1;j<=v;j++){
            dist[i][j]=INF;
        }
    }

    //Init dist
    for(int i=0; i<e; i++){
        int st, ed, d;
        cin >> st >> ed >> d;
        dist[st][ed] = d;
    }

    //floyd algorithm
    for(int k=1; k<=v; k++){
        for(int i=1;i<=v;i++){
            for(int j=1;j<=v;j++){
                dist[i][j] = min(dist[i][j],dist[i][k]+dist[k][j]);
            }
        }
    }

    //find shortest cycle
    int ans = INF;
    for(int i=1;i<=v;i++){
        ans = min(ans, dist[i][i]);
    }
    if(ans == INF) ans = -1;
    cout << ans;

    return 0;
}

 

결과 및 후기

초기 제출 시 INF 값 설정을 생각보다 작게 잡아서 채점 시 64%에서 오답이 발생했었다. 해당 INF 값을 더 크게 설정하니 모든 케이스를 통과할 수 있었다.