[c++] BOJ 1238 :: 파티

난이도 : 골드 3

걸린 시간 : 45분

문제

파티 문제 바로가기

문제

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.

어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

 

풀이

• 모든 점에서 X까지의 시간과 X에서 모든 점까지의 시간을 구해야 한다.
• 다익스트라는 1개의 점으로부터 모든 점까지의 최단 시간을 구해주기 때문에, N번 수행해야 원하는 결과를 얻을 수 있다.
  • 다익스트라의 시간복잡도는 ElogE 이므로 NMlogM 의 시간복잡도가 필요하고
  • 10^7 정도의 시간복잡도이다.
• 플로이드 와샬을 써보자.
  • 플로이드 와샬은 i부터 j까지의 경로를 i부터 k, k부터 j까지의 경로와 비교하여 갱신하는 방법이다.
  • 플로이드 와샬의 시간복잡도는 V^3 이므로 10^9의 시간복잡도가 필요하다.
  • 시간복잡도에 V만 들어가기 때문에 E(간선의 수)가 클 때 사용하면 좋다.

 

코드

<다익스트라 코드>

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

using namespace std;

int main() {

    // 입력
    int N, M, X;
    cin >> N >> M >> X;

    vector<pair<int, int>> path[10001]; // 출발 => (도착, 시간)
    for (int i = 0; i < M; i++) {
        int start, end, value;
        cin >> start >> end >> value;
        path[start].push_back(make_pair(end, value));
    }

    // 초기화
    int memo[1001][1001];
    fill(&memo[0][0], &memo[1000][1000], 1e9);

    for (int i = 1; i <= N; i++) {
        // i : 시작점
        priority_queue<pair<int, int>> que;
        que.push(make_pair(0, i)); // 시간, 노드
        memo[i][i] = 0;

        while (!que.empty()) {
            pair<int,int> tmp = que.top();
            int time = -tmp.first; int start = tmp.second;
            que.pop();
            if (memo[i][start] < time)
                continue;

            vector<pair<int, int>> canGo = path[start];
            for (int j = 0; j < canGo.size(); j++) {
                int time2 = canGo[j].second; int end = canGo[j].first;
                if (memo[i][end] > memo[i][start] + time2) {
                    memo[i][end] = memo[i][start] + time2;
                    que.push(make_pair(-memo[i][end], end));
                }
            }
        }
    }

    // 학생들의 소요시간 측정
    int res = -1;
    for (int i = 1; i <= N; i++) {
        int value = memo[i][X] + memo[X][i];
        if (value > res)
            res = value;
    }

    cout << res << '\n';
}

 

<플로이드 와샬 코드>

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

using namespace std;


int main() {
    // 9시 시작 43분 끝
    // 방향이 있는 그래프
    // 오고 가기 (start => X => start)
    // 다익스트라 n번 or 플로이드 와샬
    // 가장 오래걸리는 학생

    // 초기화
    // memset(memo, 1e9, sizeof(memo));
    int memo[1001][1001];
    fill(&memo[0][0], &memo[1000][1000], 1e9);

    // 입력
    int N, M, X;
    cin >> N >> M >> X;

    for (int i = 0; i < M; i++) {
        int start, end, value;
        cin >> start >> end >> value;
        memo[start][end] = value;
    }

    for (int i = 1; i <= N; i++) {
        memo[i][i] = 0; // 대각선은 0
    }

    // 아래의 순서 지켜야 제대로 작동
    for (int k = 1; k <= N; k++) { // 거쳐가는 노드
        for (int i = 1; i <= N; i++) { // 출발
            for (int j = 1; j <= N; j++) { // 도착
                // i,j 와 i,k + k,j 비교
                memo[i][j] = min(memo[i][j], memo[i][k] + memo[k][j]);
            }
        }
    }

    // 학생들의 소요시간 측정
    int res = -1;
    for (int i = 1; i <= N; i++) {
        int value = memo[i][X] + memo[X][i];
        if (value > res)
            res = value;
    }

    cout << res << '\n';
}

 

<테스트케이스>

5 8 1
1 4 1
4 5 5
1 3 2
3 1 1
4 2 4
2 4 4
5 3 6
3 2 3
=> 21

 

생각해볼 것

• E(간선의 수)가 매우 크면 플로이드 와샬을 이용하는 것이 낫다.
  • 다익스트라 : EVlogE
  • 플로이드와샬 : V^3

 

결과

위가 플로이드 와샬, 아래가 다익스트라이다.