[알고리즘 문제] 백준1238 - 파티

www.acmicpc.net/problem/1238

1238번: 파티

N개의 집이있고 서로의 집을 이동하는데 시간이 다를때(a->b,b->a는 서로 다름) 하나의 집으로 모이는데 가장 오랜 시간을 걸리는 시간을 구하는 문제입니다. 문제 분류는 다익스트라 알고리즘으로 되어있는데 저는 플로이드 와샬 알고리즘으로 풀었습니다.

 

두개의 알고리즘 모두 최단거리를 구하는 알고리즘 이지만, 조금 다릅니다.

다익스트라 알고리즘 : 하나의 정점에서 다른 정점으로 가는 최단거리(1차원 배열)

플로이드 와샬 알고리즘 : 모든 정점에서 모든 정점으로 가는 최단거리(2차원 배열)

 

다익스트라로 풀 경우 n번 반복해야 하지만 플로이드 와샬 알고리즘의 경우 N^3으로 한번에 구할 수 있습니다. N의 최대값이 1000이지만 다행히 시간초과가 안나오네요. 만약 시간초과가 나오게 되면 다익스트라 알고리즘을 수행하면 되는데 이때 수행시간은 한번 수행될때마다 NlogN이 걸리고 N번 반복해야 하기 때문에 N^2logN시간이 걸리겠습니다.

 

두개의 알고리즘으로 모두 계산해보았고 그 결과값은 서로 동일합니다.

 

#include <iostream>
#include <algorithm>

using namespace std;

int main()
{
    int graph[1001][1001];

    int V, E, X;

    cin >> V >> E >> X;
    int a, b, c;

    for (int i = 1; i <= V; i++)
    {
        for (int j = 1; j <= V; j++)
        {
            graph[i][j] = 987654321;
        }
    }

    for (int i = 0; i < E; i++)
    {
        cin >> a >> b >> c;
        graph[a][b] = c;
    }

    for (int via = 1; via <= V; via++)
    {
        for (int start = 1; start <= V; start++)
        {
            for (int end = 1; end <= V; end++)
            {
                if (graph[start][via] + graph[via][end] < graph[start][end])
                {
                    graph[start][end] = graph[start][via] + graph[via][end];
                }
            }
        }
    }

    int ans = 0;
    for (int i = 1; i <= V; i++)
    {
        if (i == X)
        {
            continue;
        }
        ans = max(ans, graph[i][X] + graph[X][i]); // 왕복시간을 구함
    }
    cout << ans << endl;
    return 0;
}