백준 5719 거의 최단 경로

작성일 | In |

Problem : 거의 최단 경로

유형 : 다익스트라

문제 해석

  • 최단 경로에 해당하는 경로를 피하고, 목적지에 도달하는 두번째 최단 경로를 찾아라.

문제 재해석

  • 한 점에서 부터의 최단 경로를 구하는 문제이다.
  • 다익스트라로 해결이 가능하다.

해결 전략

  • 단순히 최단 경로를 하나를 구하는 것은 쉽다.
  • 하지만, 최단 경로가 여러개인 경우를 처리해 주어야 한다.

img

  • 이것을 해결하기 위해, 도착점 부터 시작점 까리의 가중치를 역추적 해나간다.
  • 목적지 지점까지 소비한 비용과
  • 목적지 이전 지점 까지 오는데 소비한 비용 + 목적지 이전 지점에서 목적지까지의 경로 이동 비용을 비교한다.
  • 만약 두 값이 같다면, 해당 경로는 최단 경로가 된다.

설계

  • 다익스트라를 통해 목적지 까지의 최단 경로 가중치를 구한다.
  • BFS 를 통해 목적지부터, 시작점 까지의 가중치를 비교해보면 거슬러 올라간다.
  • 만약 최단 거리에 해당되는 경로를 찾았다면, 해당 경로를 지운다.

구현

  • 두가지 방법으로 구현하였다.

첫번쨰 방볍

  • vector 를 이용하여 인접 리스트를 만들고, 각 정점 끼리의 가중치를 관리하는 인접 행렬을 두고 관리했다.

두번쨰 방법

  • 장소의 수가 500이다. 즉, 모든 장소들끼리 연결되어 있어도 500P2 밖에 되지 않는다.
  • 이점을 이용하여, 도시 간의 관계를 바로 인접 행렬로 관리하고, 최단 경로의 경우 INF 값을 주어 삭제 하였다.

주의할 점

  • 최단 경로가 여러개일 수 있고, 그 최단경로가 중복되어 사용 될 수 있다.
  • 예시를 들어보겠다. 1 이 출발지 , 5 가 목적지 일때
1
2
1 > 3 > 5
1 > 4 > 3 > 5
  • 위와 같은 경우, 첫번 3 > 5가 중복되는 경우를 처리해야한다.
  • 단순히 첫번째 다익스트라를 통해 나온 경로를 방문 표시 해버린다면 3 > 5 가 방문 표시되어 1 > 4 에 대한 처리가 되지 않는다.
  • 비교하는 과정에서 INF를 더해 발생하는 overflow를 조심해야 한다.

첫번째 방법 코드

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117

#include <bits/stdc++.h>
#define pii pair<int,int>
using namespace std;

const int INF = INT_MAX;
int n, m, st, ed;
int cost[502];
int visitedCost[502][502];

vector<pii> node[502];

void VisitedMarking() {
    // 끝 지점부터, 
    // (시작점 -> 도착점의 비용) + (시작점까지의 최단비용) == (도착점까지의 최단 비용) 을 BFS를 통해 확인한다.
    queue<int> q;
    q.push(ed);

    while (!q.empty()) {
        int cur = q.front();    q.pop();

        for (int pre = 0; pre < n; ++pre) {
            if (visitedCost[pre][cur] == INF) continue;
            if (visitedCost[pre][cur] + cost[pre] != cost[cur]) continue;

            visitedCost[pre][cur] = INF;
            q.push(pre);
        }
    }
}

void CostReset() {
    for (int i = 0; i < n; ++i) {
        cost[i] = INF;
    }
}

int Dijkstra() {
    priority_queue<pii, vector<pii>, greater<pii>> pq;

    CostReset();
    cost[st] = 0;
    pq.push({ 0, st });

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

        if (curCost != cost[curSpot]) continue;

        for (auto nxt : node[curSpot]) {
            int nxtCost = curCost + nxt.first;
            int nxtSpot = nxt.second;
            if (visitedCost[curSpot][nxtSpot] == INF) continue;

            if (nxtCost < cost[nxtSpot]) {
                cost[nxtSpot] = nxtCost;
                pq.push({ nxtCost, nxtSpot });
            }
        }
    }
    return cost[ed];
}

int Solve() {
    int minCost = Dijkstra();
    if (minCost == INF) return -1;
    VisitedMarking();

    while (1) {
        int secondCost = Dijkstra();
        if (secondCost == INF) return -1;    // 경로가 없거나, 모든 경로가 최단 경로인 경우.
        if (minCost != secondCost) return secondCost;
    }
    return -1;
}

void InputPath() {
    int a, b, _cost;
    for (int i = 0; i < m; ++i) {
        cin >> a >> b >> _cost;
        node[a].push_back({ _cost,b });
        visitedCost[a][b] = _cost;
    }
}

void PathReset() {
    for (int i = 0; i < n; ++i) {
        node[i].clear();
        for (int ii = 0; ii < n; ++ii) {
            visitedCost[i][ii] = INF;
        }
    }
}

void Input() {
    while (1) {
        cin >> n >> m;
        if (n == 0 and m == 0) break;
        cin >> st >> ed;
        PathReset();
        InputPath();
        cout << Solve() << "\n";
    }
}

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

    Input();

    return 0;
}

두번째 방법 코드

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
#include <bits/stdc++.h>
#define pii pair<int,int>
using namespace std;

const int INF = INT_MAX;
int n, m, st, ed;
int cost[502];
int node[502][502];

void VisitedMarking() {
    queue<int> q;
    q.push(ed);

    while (!q.empty()) {
        int cur = q.front();    q.pop();

        for (int pre = 0; pre < n; ++pre) {
            if (node[pre][cur] == INF) continue;
            if (node[pre][cur] + cost[pre] != cost[cur]) continue;

            node[pre][cur] = INF;
            q.push(pre);
        }
    }
}

void CostReset() {
    for (int i = 0; i < n; ++i) {
        cost[i] = INF;
    }
}

int Dijkstra() {
    priority_queue<pii, vector<pii>, greater<pii>> pq;

    CostReset();
    cost[st] = 0;
    pq.push({ 0, st });

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

        if (curCost != cost[curSpot]) continue;

        for (int nxtSpot = 0; nxtSpot < n; ++nxtSpot) {
            if (node[curSpot][nxtSpot] == INF) continue;
            int nxtCost = curCost + node[curSpot][nxtSpot];

            if (nxtCost < cost[nxtSpot]) {
                cost[nxtSpot] = nxtCost;
                pq.push({ nxtCost, nxtSpot });
            }
        }
    }
    return cost[ed];
}

int Solve() {
    int minCost = Dijkstra();
    if (minCost == INF) return -1;
    VisitedMarking();

    while (1) {
        int secondCost = Dijkstra();
        if (secondCost == INF) return -1;
        if (minCost != secondCost) return secondCost;
    }
    return -1;
}

void InputPath() {
    int a, b, _cost;
    for (int i = 0; i < m; ++i) {
        cin >> a >> b >> _cost;
        node[a][b] = _cost;
    }
}

void PathReset() {
    for (int i = 0; i < n; ++i) {
        for (int ii = 0; ii < n; ++ii) {
            node[i][ii] = INF;
        }
    }
}

void Input() {
    while (1) {
        cin >> n >> m;
        if (n == 0 and m == 0) break;
        cin >> st >> ed;
        PathReset();
        InputPath();
        cout << Solve() << "\n";
    }
}

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

    Input();

    return 0;
}

디버깅

  • 주의할점 에서 언급한 내용을 놓쳤었다.

피드백

  • BFS를 통해 최단경로를 다 찾는법을 배웠다.
  • 요새 밤에 푸는 문제가 더 잘 안 풀리는것 같다.
  • 첫 WA를 받고 문제점은 바로 찾았으나, 아이디어를 내가 싫어, 자고 일어난 뒤 다시 시도하니 금방 풀렸다..