[백준 1238] 파티 (C++)

1238번 문제

풀이

N개의 마을에는 각각 한 명의 학생이 살고 있고, 입력 받은 X번 마을에서 파티가 열린다. 모든 학생들의 이동거리는 최단거리여야 한다.
N명의 학생들 중 (i번째 마을 -> x번 마을) + (x번 마을 -> i번째 마을) 시간이 가장 긴 학생의 소요시간을 출력하면 된다.

1. Floyd Warshall Algorithm
   '모든 정점'에서 '모든 정점'으로의 최단경로
   출발노드에서 도착노드로 가는 거리와 다른 노드를 거쳐서 도착노드를 가는 거리를 비교하며 각 노드로 가는 최단경로를 arr 배열에 넣는다.
   크기가 n인 ans배열 각각에 arr[i][x-1] (i번째 마을에서 x번째 마을로 가는 최단거리) + arr[x-1][i] (x번째 마을에서 i번째 마을로 가는 최단거리) 값을 넣어준 후 ans배열 중 가장 큰 값을 답으로 출력한다.

2. Dijkstra Algorithm
   '한 정점'에서 '모든 정점'으로의 최단경로
   인접 리스트를 활용하여 연결된 정점들의 정보를 저장해준다. 우선순위 큐를 사용하여 인접 노드들 중 거리가 가까운 노드부터 처리한다. 인접 노드를 거쳐서 가는 거리가 기존 거리보다 짧다면 해당 거리를 최단경로로 설정한다.

   (1) i에서 x로의 최단경로
   dijkstra 함수에 i값 (1 ~ n)을 인자로 각각 넣어주며 i에서 모든 정점으로의 최단경로를 dst배열에 넣어준다. 필요한 값은 i에서 x로 가는 거리이므로 n개의 dst[x] 값을 ans 배열에 순서대로 넣어준다.

   (2) x에서 i로의 최단경로
   dijkstart 함수에 x값을 인자로 넣어주고 x에서 모든 정점으로의 최단경로를 ans 배열 값에 더해준다.
   ans 배열 중 가장 큰 값을 답으로 출력한다.

처음 문제를 읽었을 때 다익스트라 알고리즘으로 문제를 풀어야겠다고 생각했다. 하지만 다익스트라 구현 방식이 제대로 기억이 나지 않아서,, 일단 플로이드와샬로 풀어보기로 !
N의 최댓값이 1,000이다보니 3중 for문을 사용하는 플로이드와샬로는 풀지 못할 것이라는 생각도 들었지만 ,,, 일단 제출해보기로 했고 통과하긴 했다!
통과는 했지만 찝찝한 마음에 다익스트라 알고리즘 복습 후 재제출했다.

소스 코드

1. Floyd Warshall Algorithm version

//BOJ 1238번: 파티
#include <iostream>
#include <algorithm>
#define MAX 1000
#define INF 1e9
using namespace std;

int arr[MAX][MAX];

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int n, m, x, start, end, t, maximum=-1;
    cin >> n >> m >> x;

    for(int i = 0 ; i < n ; i++){
        for(int j = 0 ; j < n ; j++){
            if(i != j) arr[i][j] = INF;
        }
    }

    for(int i = 0 ; i < m ; i++){
        cin >> start >> end >> t;
        arr[start-1][end-1] = t;
    }

    for(int k = 0 ; k < n ; k++){ //거쳐가는 노드
        for(int i = 0 ; i < n ; i++){ //출발 노드
            for(int j = 0 ; j < n ; j++){ //도착 노드
                if(arr[i][k] + arr[k][j] < arr[i][j]){
                    arr[i][j] = arr[i][k] + arr[k][j];
                }
            } 
        }
    }
    
    int ans[n];

    for(int i = 0 ; i < n ; i++){
        ans[i] = arr[i][x-1] + arr[x-1][i];
        maximum = max(ans[i], maximum);
    }

    cout << maximum;

    return 0;
}

2. Dijkstra Algorithm version

//BOJ 1238번: 파티
#include <iostream>
#include <queue>
#include <algorithm>
#define MAX 1001
#define INF 1e9
using namespace std;

vector<pair<int, int>> graph[MAX];
int dst[MAX], ans[MAX];
int n, m, x, s, e, t;

void dijkstra(int start){
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int,int>>> pq; //거리, 노드
    pq.push(make_pair(0, start));
    dst[start] = 0;

    while(!pq.empty()){
        int cost = pq.top().first;
        int now = pq.top().second;
        pq.pop();

        for(int i = 0 ; i < graph[now].size() ; i++){
            int next = graph[now][i].first;
            int nCost = graph[now][i].second;
            
            if(cost+nCost < dst[next]){
                dst[next] = cost + nCost;
                pq.push(make_pair(cost + nCost, next));
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> m >> x;

    for(int i = 1 ; i <= n ; i++){
        dst[i] = INF;
    }

    for(int i = 0 ; i < m ; i++){
        cin >> s >> e >> t;
        graph[s].push_back(make_pair(e, t));
    }

    //i to x
    for(int i = 1 ; i <= n ; i++){
        for(int j = 1 ; j <= n ; j++){
            dst[j] = INF;
        }
        dijkstra(i);
        ans[i] = dst[x];
    }

    for(int i = 1 ; i <= n ; i++) dst[i] = INF;

    // start x
    dijkstra(x);

    for(int i = 1 ; i <= n ; i++){
        ans[i] += dst[i];
    }

    cout << *max_element(ans+1, ans+n+1);

    return 0;
}