백준 1602 도망자 원숭이

작성일 | In |

Problem : 도망자 원숭이

유형 : 플로이드 워셜

문제 해석

  • 원숭이가 목적지까지 도달하는 가장 짧은 시간을 구하라.

문제 재해석

  • 원숭이는 최단 경로로 이동하는 것을 원한다.
  • 각 도시간 이동할때 가중치가 입력으로 들어온다.
  • 멍멍이는 원숭이를 최고 오래 괴롭힐 수 있는 도시 하나를 택한다.

해결 전략

  • 목적지 쿼리가 1만개까지 나올 수 있다.
  • 플로이드 워셜을 통해 최단 거리를 찾는다.

  • 이때 멍멍이가 괴롭히는 시간도 고려해야 한다.

  • 플로이드 워셜에서 방문하는 도시를 멍멍이가 가장 적게 괴롭히는 곳부터 시작한다.
  • 왜냐하면, 멍멍이가 괴롭히는 가중치가 가장 작은곳 부터 진행해야, 다른 경로를 갱신할 때, 이전 정보만 가지고 갱신 할 수 있게 된다.
  • 즉 가중치가 적은 정점만을 이용해서 최단거리를 갱신했으므로, 이후 작업에서 이전 정보를 토대로 최단거리를 갱신할 수 있게 된다.

구현, 설계

  • 기본적인 플로이드 워셜 세팅을 한다.
  • 멍멍이가 선택할 위치를 dog_cost로 저장한다.
  • 플로이드 워셜 중간 지점은 멍멍이가 가장 적게 괴롭히는 도시 부터 시작한다.
  • 플로이드 워셜 과정에서, 중간 지점을 방문할 경우, 두 지점 사이에서 가장 가중치가 높은 지점을 선택한다.
  • 새롭게 가는곳이 최단 경로인 경우, 갱신한다.

주의할점

  • 플로이드 워셜의 원리를 정확히 파악해야 한다.
  • 가중치가 없는 경우에는 방문하는 도시의 순서가 중요하지 않으나, 가중치가 있는 경우에는 가장 적은 도시부터 방문 해야한다.

디버깅

  • 예제도 제대로 나오지 않던 코드를 제출해서 틀렸었다.
  • 가중치를 고려하지 않고 플로이드를 돌렸었다.

코드

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
74
75
76
77
78
79
80
#include <bits/stdc++.h>
#define pii pair<int,int>

using namespace std;

const int INF = 1e9;
int cost[502][502], dog_cost[502][502];
int dog[10002];
vector<pii> dog_p;

int n, m, q;

void Floyd() {
    for (int i = 0; i < n; ++i) {
        int visit = dog_p[i].second;

        for (int s = 1; s <= n; ++s) {
            for (int e = 1; e <= n; ++e) {
                int dog_attack = max(dog_cost[s][visit], dog_cost[visit][e]);
                int cur_dog_attack = dog_cost[s][e];

                if (cost[s][visit] + cost[visit][e] + dog_attack < cost[s][e] + cur_dog_attack) {
                    cost[s][e] = cost[e][s] = cost[s][visit] + cost[visit][e];
                    dog_cost[s][e] = dog_cost[e][s] = dog_attack;
                }
            }
        }
    }
}


void Solve() {
    Floyd();

    int s, e;
    while (q--) {
        cin >> s >> e;
        if (cost[s][e] == INF) cout << -1 << "\n";
        else cout << cost[s][e] + dog_cost[s][e] << "\n";
    }
}

void Init() {
    for (int i = 1; i <= n; ++i) {
        for (int ii = 1; ii <= n; ++ii) {
            if (i == ii) continue;
            cost[i][ii] = INF;
        }
    }
}

void Input() {
    cin >> n >> m >> q;
    Init();
    for (int i = 1; i <= n; ++i) {
        cin >> dog[i];
        dog_p.push_back({ dog[i],i });
    }

    sort(dog_p.begin(), dog_p.end());

    int a, b, _cost;
    while (m--) {
        cin >> a >> b >> _cost;
        cost[a][b] = cost[b][a] = _cost;
        dog_cost[a][b] = dog_cost[b][a] = max(dog[a], dog[b]);
    }
}

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

    Input();
    Solve();

    return 0;
}

피드백

  • 사실 혼자서 해결방법을 떠올리지 못했다.
  • 질문 게시판의 kks227 님의 답변을 보고, 해결하였다.
  • 알고리즘을 공부할 때 그 원리를 정확히 파악 해두자.