[백준] 20160 야쿠르트 아줌마 야쿠르트 주세요 (C++)

작성일 Edited on In , Views: Disqus:

문제 링크 : https://www.acmicpc.net/problem/20160

풀이 및 구현

문제를 보면 최단 시간에 대한 이야기가 나오는데 여러 지점간 최단 시간을 구해야 되는 문제라 생각해서 제일 먼저 플로이드-워셜 알고리즘을 떠올렸다. 모든 지점 간의 최단 거리를 미리 구해놓으면 야구르트 아줌마가 지점별 도달 시간을 쉽게 구할 수 있고 내가 해당 시간 안에 도착할 수 있는지도 빠르게 구할 수 있다.

하지만 문제의 제약 조건을 확인하면 정점 $V$의 조건이 $(1 \leq V \leq 10000)$ 이므로 시간 복잡도가 $O(N^3)$인 플로이드-워셜을 쓰기에는 부적절하다는 것을 할 수 있다.

최단 거리를 구해야하는 횟수는

  1. 야쿠르트 아줌마가 지점을 총 10군데 방문하므로 9번
  2. 내가 각 지점까지 가야하는 횟수 10번

이므로 최대 19번 구하면 된다.

그러므로 다익스트라 알고리즘을 이용하면 충분하다.

다익스트라 함수는 출발지, 도착지를 넣으면 거리를 반환하는 형태로 구성하였다.

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
typedef long long ll;
constexpr ll INF = LLONG_MAX;

int V, E;
vector<vector<array<ll, 2>>> adj;

ll Dijkstra(int s, int e) {
    vector<ll> dist(V, INF);
    dist[s] = 0;
    priority_queue<array<ll, 2>> pq;
    pq.push({0, s});


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

        if (cur_dist != dist[cur_node]) continue;

        for (const auto& [nxt_node, nxt_dist] : adj[cur_node]) {
            if (cur_dist + nxt_dist < dist[nxt_node]) {
                dist[nxt_node] = cur_dist + nxt_dist;
                pq.push({-(cur_dist + nxt_dist), nxt_node});
            }
        }
    }

    return dist[e];
}

야구르트 아줌마의 각 지점별 도착 시간은 다음과 같이 구했다.

vector<int> v : 지점 별 노드 번호

vector<ll> d : 지점 별 도착 시간

cur : 현재 야구르트 아줌마의 위치 (시작은 0)

로 하고 1부터 9번째 지점까지 돌면서 v[cur]에서 v[i]로 이동할 수 없으면 d[i]를 -1로 바꾸고,

이동할 수 있으면 d[i]는 현재 노드에 도착한 시간인 d[cur]에 dist를 더해주고 cur를 i로 바꿔 이동해주었다. 이 때 오버플로우가 발생할 수 있어 long long 형식으로 저장해주어야 한다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
vector<int> v(10);
vector<ll> d(10, 0);
for (int& i : v) cin >> i;
int cur = 0;
for (int i = 1; i < 10; i++) {
    ll dist = Dijkstra(v[cur] - 1, v[i] - 1);
    
    // v[cur] -> v[i]로 이동할 수 없을 때
    if (dist == INF) {
        d[i] = -1;
    }
    
    // v[cur] -> v[i]로 이동할 수 있으므로 v[i]로 이동한다.
    else {
        d[i] = d[cur] + dist;
        cur = i;
    }
}

각 지점별로 야쿠르트 아줌마의 도착 시간을 구했다면 내 위치로부터 각 지점까지 최단 시간을 구하고 해당 지점에 갈 수 있고, 야구르트 아줌마와 같은 시간 혹은 이전 시간에 도착했다면 ans 벡터에 넣어주었다.

이후 ans를 정렬하여 번호가 가장 작은 정점을 출력하면 답을 얻을 수 있다.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int me; cin >> me;
vector<int> ans;
for (int i = 0; i < 10; i++) {

    // 야쿠르트 아줌마가 가지 않는 곳은 무시
    if (d[i] == -1) continue;
    
    // 야쿠르트 아줌마보다 일찍 갈 수 있는지 확인한다.
    if (Dijkstra(me - 1, v[i] - 1) <= d[i]) ans.push_back(v[i]);
}
sort(ans.begin(), ans.end());

if (ans.empty()) cout << -1;
else cout << ans.front();

코드

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
73
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
constexpr ll INF = LLONG_MAX;

int V, E;
vector<vector<array<ll, 2>>> adj;

ll Dijkstra(int s, int e) {
    vector<ll> dist(V, INF);
    dist[s] = 0;
    priority_queue<array<ll, 2>> pq;
    pq.push({0, s});


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

        if (cur_dist != dist[cur_node]) continue;

        for (const auto& [nxt_node, nxt_dist] : adj[cur_node]) {
            if (cur_dist + nxt_dist < dist[nxt_node]) {
                dist[nxt_node] = cur_dist + nxt_dist;
                pq.push({-(cur_dist + nxt_dist), nxt_node});
            }
        }
    }

    return dist[e];
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);

    cin >> V >> E;
    adj.assign(V, vector<array<ll, 2>>());

    for (int i = 0; i < E; i++) {
        ll s, e, w; cin >> s >> e >> w;
        adj[s - 1].push_back({e - 1, w});
        adj[e - 1].push_back({s - 1, w});
    }

    vector<int> v(10);
    vector<ll> d(10, 0);
    for (int& i : v) cin >> i;
    int cur = 0;
    for (int i = 1; i < 10; i++) {
        ll dist = Dijkstra(v[cur] - 1, v[i] - 1);
        if (dist == INF) {
            d[i] = -1;
        }
        else {
            d[i] = d[cur] + dist;
            cur = i;
        }
    }

    int me; cin >> me;
    vector<int> ans;
    for (int i = 0; i < 10; i++) {
        if (d[i] == -1) continue;
        if (Dijkstra(me - 1, v[i] - 1) <= d[i]) ans.push_back(v[i]);
    }
    sort(ans.begin(), ans.end());

    if (ans.empty()) cout << -1;
    else cout << ans.front();
}

후기

img.png

최단 거리는 int 범위 내에서 구해져서 오버플로우를 생각하지 않았는데 야쿠르트 아줌마가 이동하면서 최단 거리가 누적될 때 오버플로우가 일어난다는 것을 생각하지 못해 틀렸다.