백준 1238 : 파티 / 플로이드 워셜 알고리즘

문제

 

문제 분석

노드간의 최단거리를 만들어 두고, 파티 노드 X로 오고 가는 거리의 최댓값을 구하는 문제였다. 즉, 모든 노드간의 거리가 최단거리라고 할 때 A -> X -> A의 최댓값을 구하는 문제였다.

모든 노드로 부터 모든 노드로의 최단거리 문제를 구하는 문제였으므로 Floyd-warshall 알고리즘을 적용시켜서 풀면 된다고 생각했다.

근데 ㅋㅋㅋㅋ 적용시키면 풀릴것같은데 구현을 까먹었어서 잠시 현타가 왔었다. 아직 내 지식이 아닌가보다 하고 다시 서치했다. 알고리즘의 핵심은 모든 경로에 대해서 모든 노드를 거쳐갈 때를 확인하는 것이다.

 

즉, 1->3이라는 경로가 존재할 때 1->(2,4....) ->3 와 같이 그 외의 모든 노드를 중간에 넣어보면서 그 노드가 들어갈 때 총 거리가 더 줄어드는지 확인하는 것이다.  

참고로 이 알고리즘의 복잡도는 O(V^3)이고 다익스트라는 O(E + VlogV)이다.

코드

#include<stdlib.h>
#include<iostream>
#include<string.h>
#include<string>
#include<list>
#include<vector>
#include<stack>
#include<queue> // priority_queue 포함
#include<set>
#include<unordered_set>
#include<map>
#include<unordered_map>

#include<algorithm>
#include<math.h>
#include<climits> // 자료형 limit포함

using namespace std;

typedef long long int lld;
typedef unsigned long long int uld;
typedef unsigned int ui;

const int MY_INT_MAX = 1000000000;

int input_map[1001][1001] = {0};
int dp[1001][1001] = {0};

void solution()
{
    // code
    int n,m,x;
    cin >> n >> m >> x;
    for(int i=0; i<=n; i++) for(int j=0; j<=n; j++) if(i != j) input_map[i][j] = MY_INT_MAX;
    for(int i=0; i<m; i++)
    {
        int a,b,c;
        cin >> a >> b >> c;
        input_map[a][b] = c;
    }

    for(int k=1; k<=n; k++)
    {
        for(int i=1; i<=n; i++)
        {
            for(int j=1; j<=n; j++)
            {
                if(input_map[i][j] > input_map[i][k] + input_map[k][j])
                    input_map[i][j] = input_map[i][k] + input_map[k][j];
            }
        }
    }
    int my_max = -1;
    for(int i=1; i<=n; i++) if(i != x) my_max = max(my_max, input_map[i][x] + input_map[x][i]);
    cout << my_max;
}

int main ()
{
    iostream::sync_with_stdio(0); // 이제 C stdio의 입출력 사용 불가
    cin.tie(NULL);
    cout.tie(NULL); // 개행도 \n로 하도록 하자.
    solution();
    return 0;
}// code

개선점?

알고리즘보단 알고리즘의 본질을 더 보도록하자....