백준 1238 파티 [C++]

작성일 | In |

Problem : 파티

유형 : 다익스트라

문제 해석

  • 학생들은 파티에 참여하고, 마을에 돌아간다.
  • 단 방향 그래프이다.
  • 각각의 학생들은 파티 장소로 이동할때, 마을로 돌아갈때 전부 최단거리로 움직인다.
    • 이중 가장 오래 시간이 걸리는 학생을 구하라.

해결 전략

  • 파티 장소에서 마을에 이동하는 최단 거리를 찾는다.
    • 시작점을 파티 장소로 잡고, 다익스트라를 진행한다.
  • 마을에서 파티장소로 이동하는 최단 거리를 찾는다.
    • 원래는 각 마을을 시작점으로, 다익스트라를 최대 1000번 진행하려고 했다.
      • 하지만 굉장히 비효율적인 방법인것 같아서 다른 방법을 찾아 보았다.
    • 간선을 전부 뒤집고, 시작점을 파티 장소로 잡고, 다익스트라를 진행한다.
      • 이렇게 하면, 최단거리 테이블에 있는 내용은 각 마을에서 부터 파티 장소까지의 최단거리가 저장된다.
      • 즉 최대 1000번의 다익스트라를 1번으로 줄일 수 있게된다.

설계, 구현

  • 노드와 간선관의 관계를 세팅한다.
    • 간선을 뒤집어서도 세팅한다.
  • 다익스트라를 두번 진행한다.
    • 파티룸에서 출발할때는 정방향 간선 정보를 넣는다.
    • 파티룸으로 이동할때는 역방향 간선 정보를 넣는다.
  • 왕복거리가 가장 큰 값을 구한다.

주의할 점

  • 노드 시작은 1번부터이다.
    • 최단거리 테이블의 크기는 n+1 개로 해주어야 한다.

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include <bits/stdc++.h>
#define pii pair<int, int>

using namespace std;

const int MAX_NODE_COUNT = 1001;
const int INF = INT_MAX;
int dist[MAX_NODE_COUNT];
int n, m, partyNode;

vector<pii> forwardNode[MAX_NODE_COUNT];
vector<pii> reverseNode[MAX_NODE_COUNT];

vector<int> dijkstra(vector<pii> node[MAX_NODE_COUNT]) {
    priority_queue < pii, vector<pii>, greater<pii> > pq;

    vector<int> dist(n + 1, INF);
    dist[partyNode] = 0;
    pq.push({ 0, partyNode });

    while (!pq.empty()) {
        auto cur = pq.top(); pq.pop();
        int curCost = cur.first;
        int curNode = cur.second;

        if (dist[curNode] != curCost) continue;
        for (pii next : node[curNode]) {
            int nextCost = next.first + curCost;
            int nextNode = next.second;

            if (nextCost < dist[nextNode]) {
                dist[nextNode] = nextCost;
                pq.push({ nextCost, nextNode });
            }
        }
    }
    return dist;
}

void input() {
    cin >> n >> m >> partyNode;
    while (m--) {
        int s, e, cost;
        cin >> s >> e >> cost;
        forwardNode[s].push_back({cost, e});
        reverseNode[e].push_back({cost, s});
    }
}

void solve() {
    input();
    vector<int> fromPartyRoomDist = dijkstra(forwardNode);
    vector<int> toPartyRoomDist = dijkstra(reverseNode);

    int answer = 0;

    for (int i = 1; i <= n; ++i) {
        answer = max(answer, fromPartyRoomDist[i] + toPartyRoomDist[i]);
    }
    cout << answer << "\n";
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);  cout.tie(NULL);
    //freopen("input.txt", "r", stdin);

    solve();

    return 0;
}

피드백

  • 과거 무식하게 플로이드로 풀었던 문제이다.
  • 다익스트라를 1000번에서 1번으로 줄이는 아이디어가 바로 떠오르지 않았다.
    • 나중에 다시 풀어볼 문제.