백준 5719, 거의 최단경로

처음으로 제대로된 플레를 혼자서 풀어본 느낌이다. 물론 힌트를 보긴 했는데...

문제

https://www.acmicpc.net/problem/5719

풀이

이 문제는 중복되는 최단 경로의 경로를 포함하지 않는 그다음으로 최단인 경로를 찾는 문제이다.

여기서 중요한 것은 거의 최단 경로는 최단 경로의 경로를 포함하지 않아야 하는 것과 이 최단 경로는 한개가 아니고 서로 경로가 중복될 수 있다는 점이다.

그래서 처음에는 다익스트라로 최단 경로를 구하고 해당 경로를 모두 제외하고 구하면 거의 최단 경로가 나오지 않을까 라는 컨셉으로 접근했다.

하지만 이렇게 할 경우에는 경로가 중복되는 최단 경로에 대한 처리를 하지 못한다.

그래서 일반적인 다익스트라에서 경로를 저장할 때 그 전 노드를 저장하는데 그 저장하는 노드를 여러개로 늘려 존재하는 최단 경로를 모두 찾고 dfs(dfs로 의도하지는 않았는데 짜고보니 dfs가 됨)로 해당 경로를 모두 제외 시켰다.

따라서 다익스트라를 할때 최소값이 갱신되는 경우 노드를 저장해야 하고, 같을 때도 다른 최단 경로를 의미하는 것이니 저장해야 한다.

그리고 나서 그 전 최단 경로를 통해 경로를 추적 할때는 마지막에 저장한 것은 항상 최소인 것이 보장되니 뒤부터 값이 최소가 아닐 때까지 경로를 제외한다. 이때 앞부터 탐색해도 간선의 개수가 적어서 그런지 시간에는 영향을 끼치지 않았다 (똑같이 52ms)

그리고 이렇게만 하면 시간 초과가 나서 node를 초기화를 할때 600으로 정적으로 해주던 것을 n만큼 초기화 하게 최적화하고, 다익스트라는 d에 도달하면 멈추게, 경로를 역추적할때는 같은 노드를 한번 초과로 방문하면 손해이므로 한번만 방문하도록 최적화해주었다.

이렇게 하니까 문제가 풀렸다. 최적화 할때는 질문 게시판의 도움을 받긴 했다.

그리고 힙을 이용한 다익스트라는 이번이 처음이었는데 꽤 복잡했다. 익숙해져야겠다.

• 이거 cost 저장하고 도착 노드부터 bfs로 최단경로 역추적하는게 정석적인 풀이라고 한다. 이게 더 좋은듯

실수

• STL 사용이 많았다. 그래서 시간이 오래걸렸다. STL 사용법을 잘 익히자
• 코드가 복잡해서 그런가 생각이후 구현하는데 시간이 오래걸렸다 (생각 끝내고 구현만 3시간 걸릴듯, 놀면서 하긴 했는데...)
• 이제부터는 최적화에 대해서도 생각을 해야하는 난이도에 오게된 것 같다. 앞으로는 무지성 초기화, 정적 선언은 자제하도록 하자
• 처음에 시간복잡도를 계산하지 못했고 문제에서도 테스트케이스의 개수를 주어지지 않아서 헤맸었다. 다 짜고보니 nlogn이라서 거의 상수시간에 돌아가서 풀린 것을 알았다.
• 벡터에 튜플쓰니까 디버깅할때 한번 클릭으로 안보이고 두번 클릭해야 보이더라 양도 많아짐. 한눈에 안보이더라... 그냥 한개로 다 쪼개는게 나을까?

코드

#define _CRT_SECURE_NO_WARNINGS

#include <iostream>
#include <vector>
#include <algorithm>
#include <tuple>
#include <queue>
#include <utility>

using namespace std;

#define COST 0
#define VISIT 1

#define DEST 0 // 도착지
#define WEIGHT 1
#define EXCEPT 2

#define NODE 0
#define INDEX 1
#define MIN_COST 2

#define TRUE 1
#define FALSE 0

vector<vector<tuple<int, int, int>>> graph(600, vector<tuple<int, int, int>>(3, make_tuple(0, 0, 0))); // 간선 관련 정보 저장
vector<vector<int>> node_info(600, vector<int>(2, 0)); // 최단 경로 관련 정보 저장
vector<vector<tuple<int, int, int>>> prev_node(600, vector<tuple<int, int, int>>(0, make_tuple(0, 0, 0))); // first : prev_node, second : 해당 edge가 들어있는 index, third : 해당 최소 비용
vector<int> prev_node_visit(600, 0);

int n, m;
int s, d;
void dijkstra() {

    int now = s;
    priority_queue<pair<int, int>> pq;

    node_info[s][COST] = 0;

    pq.push(make_pair(0, s));

    while(!pq.empty()){

        while (1) { // 힙에서 최소를 찾아 반환

            if (pq.empty()) {

                now = -1;
                break;

            }

            else if (node_info[pq.top().second][VISIT] == FALSE) {

                node_info[pq.top().second][VISIT] = TRUE;
                now = pq.top().second;
                pq.pop();

                break;

            }

            else 
                pq.pop();


        }

        if (now == -1) // pq가 비었으면 탈출
            break;

        for (int j = 0; j < graph[now].size(); j++) {

            tuple<int, int, int> now_edge = graph[now][j];

            if (get<EXCEPT>(now_edge) == TRUE) // 제외된 경로는 넘어감
                continue;

            if (node_info[get<DEST>(now_edge)][COST] > node_info[now][COST] + get<WEIGHT>(now_edge)) { // 작으면 갱신

                node_info[get<DEST>(now_edge)][COST] = node_info[now][COST] + get<WEIGHT>(now_edge);

                pq.push(make_pair(-1 * node_info[get<DEST>(now_edge)][COST], get<DEST>(now_edge))); // 코스트가 작은 순으로 정렬하기 위해 음수화

                prev_node[get<DEST>(now_edge)].push_back(make_tuple(now, j, node_info[get<DEST>(now_edge)][COST])); // 경로 역추적용

            }

            else if (node_info[get<DEST>(now_edge)][COST] == node_info[now][COST] + get<WEIGHT>(now_edge)) { // 같아도 중복된 최단 경로를 위해서 저장

                prev_node[get<DEST>(now_edge)].push_back(make_tuple(now, j, node_info[get<DEST>(now_edge)][COST]));

            }

        }

        if (now == d) // 도착지까지 수행했으면 더이상 하지 않아도 됨.
            break;

    }

}

void except_edge(int now) {

    prev_node_visit[now] = TRUE; // 이거 안넣으면 틀림.

    for (int i = prev_node[now].size() - 1; i >= 0; i--) { // 뒤에서부터 탐색하면 항상 최소 만나다가 아니면 탈출, 근데 여기까지 고치지 않아도 맞음

        if (get<MIN_COST>(prev_node[now][i]) == get<MIN_COST>(prev_node[now][prev_node[now].size() - 1])) { // 가장 마지막에 저장한 값이 최소임, 최소로 저장되어 있지 않으면 제외하지 않음.

            get<EXCEPT>(graph[get<NODE>(prev_node[now][i])][get<INDEX>(prev_node[now][i])]) = TRUE;

            if (prev_node_visit[get<NODE>(prev_node[now][i])] == FALSE)
                except_edge(get<NODE>(prev_node[now][i]));

        }

        else
            break;

    }

}


int main() {

    while (1) {

        scanf(" %d %d", &n, &m);

        if (n == 0 && m == 0) {

            break;

        }

        scanf(" %d %d", &s, &d);


        // 초기화
        for (int i = 0; i < n; i++) {

            graph[i] = vector <tuple<int, int, int>>(0, make_tuple(0, 0, 0));

            node_info[i][COST] = 2e9;
            node_info[i][VISIT] = FALSE;

            prev_node[i] = vector<tuple<int, int, int>>(0, make_tuple(0, 0, 0));

            prev_node_visit[i] = FALSE;

        }

        // 입력
        int temp1, temp2, temp3;

        for (int i = 0; i < m; i++) {

            scanf("%d %d %d", &temp1, &temp2, &temp3);

            graph[temp1].push_back(make_tuple(temp2, temp3, FALSE));

        }

        dijkstra(); // 최소 경로를 찾음

        except_edge(d); // 최소 경로에 사용된 경로를 제외함.

         // 초기화
        for (int i = 0; i < n; i++) {

            node_info[i][COST] = 2e9;
            node_info[i][VISIT] = FALSE;

            prev_node[i] = vector<tuple<int, int, int>>(0, make_tuple(0, 0, 0));

        }

        dijkstra(); // 거의 최소경로를 찾음

        if (node_info[d][COST] == 2e9)
            printf("-1\n");

        else 
            printf("%d\n", node_info[d][COST]);

    }

    return 0;

}