[BOJ - 1238] 파티 (C++)

문제

 

접근방법

학생들이 워낙 게을러서 "최단 시간"에 오고 가기를 원한다 - 다익스트라 알고리즘

 가장 오래 걸리는 학생의 소요시간 -> 함수의 반환값을 배열로 설정

(학생들이 집에서 X로 가는 거 + X에서 집으로 가는거) - 이 두 가지를 고려하면 된다.

 

(최근 다익스트라만 올리는거 같은데 맞음, 이거 공부하고 있어요.)

 

기존코드

#include <iostream>
#include <queue>
#include <vector>

#define INF 1e9

using namespace std;

// 학생 수, 도로의 수, 도착지
int N, M, X;
// 도착지, 비용
vector<pair<int, int>> adj[1001];
vector<pair<int, int>> rev_adj[1001];

vector<int> dijkstra(int start) {
    vector<int> dist(N+1, INF);
    dist[start] = 0;

    // 비용, 도착점
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> pq;
    pq.push({0, start});

    while (!pq.empty()) {
        auto [cur_dist, cur] = pq.top();
        pq.pop();

        if (cur_dist > dist[cur]) continue;

        for (auto &[next, next_dist]: adj[cur]) {
            if (cur_dist + next_dist < dist[next]) {
                dist[next] = cur_dist + next_dist;
                pq.push({dist[next], next});
            }
        }
    }

    return dist;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> M >> X;

    for (int i = 0; i < M; i++) {
        int A, B, T;
        cin >> A >> B >> T;
        adj[A].push_back({B, T});
    }

    int max_flow = 0;

    vector<int> rev_dist = dijkstra(X);
    for (int i = 1; i <= N; i++) {
        vector<int> dist = dijkstra(i);
        int result = dist[X] + rev_dist[i];

        max_flow = max(max_flow, result);
    }

    cout << max_flow << endl;

    return 0;
}

 

리팩토링 코드(GPT 교수님)

#include <bits/stdc++.h>
using namespace std;

#define INF 1e9

int N, M, X;
vector<pair<int, int>> adj[1001];       // 일반 그래프 (i → X 가는 경로)
vector<pair<int, int>> rev_adj[1001];   // 역방향 그래프 (X → i로 가는 경로)

// 다익스트라 알고리즘
vector<int> dijkstra(int start, vector<pair<int, int>> graph[]) {
    vector<int> dist(N + 1, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> pq;
    
    dist[start] = 0;
    pq.push({0, start});

    while (!pq.empty()) {
        auto [cur_dist, cur] = pq.top();
        pq.pop();

        if (cur_dist > dist[cur]) continue;

        for (auto &[next, next_dist] : graph[cur]) {
            int new_dist = cur_dist + next_dist;
            if (new_dist < dist[next]) {
                dist[next] = new_dist;
                pq.push({new_dist, next});
            }
        }
    }

    return dist;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> N >> M >> X;

    for (int i = 0; i < M; i++) {
        int A, B, T;
        cin >> A >> B >> T;
        adj[A].push_back({B, T});   // 정방향 그래프 (i → X)
        rev_adj[B].push_back({A, T}); // 역방향 그래프 (X → i)
    }

    // 다익스트라 2번만 실행
    vector<int> dist_to_X = dijkstra(X, rev_adj); // X에서 모든 정점으로 가는 거리
    vector<int> dist_from_X = dijkstra(X, adj);   // 모든 정점에서 X로 가는 거리

    int max_time = 0;
    for (int i = 1; i <= N; i++) {
        max_time = max(max_time, dist_from_X[i] + dist_to_X[i]);
    }

    cout << max_time << "\n";

    return 0;
}

 

비효율적인 다익스트라 실행을 줄이고 최적화

모든 학생들이 파티 장소 X로 가야 하므로, "모든 정점 → X" 최단 거리만 있으면 된다.

 

아니 X에서 모든 정점으로 가는 거리를 어떻게 rev_adj로 저렇게 설정해서 할 생각을 했지?

 

 

 실제로 시간이 굉장히 단축된 것을 확인할 수 있었음 (104 ms -> 0 ms는 굉장하다)

 

링크

1238번: 파티