[백준] 13907 세금

문제 주소 : www.acmicpc.net/problem/13907

13907번: 세금

문제 확인

 

다익스트라 알고리즘을 활용하여 세금 인상 전 최소비용 경로를 구하고 경로의 개수에 가중치를 두는 문제입니다. 

개인적으로 이 블로그가 설명을 잘해 둔 것 같습니다

 

다익스트라 기본 개념 : mattlee.tistory.com/50

<dijkstra의 최단="" 경로="" 알고리즘=""> 기본개념과 알고리즘</dijkstra의>

 

풀이

 

그래프 생성 시 vector와 2차원 배열을 사용해 보았습니다. 다익스트라 알고리즘 특성상 2차원 배열을 사용하면 N개의 배열을 탐색해야 하므로 메모리, 시간 모두 비효율적이라 vector 컨테이너를 활용하는 것이 좋습니다. vector 컨테이너를 사용하면 존재하는 간선만 저장하므로 탐색 시 효율적이며 메모리를 적게 사용합니다.

최적화 전 위 : 2차원 배열 그래프, 아래 : 벡터 컨테이너 그래프

다익스트라 알고리즘을 여러 번 돌려서 계산하는 방식을 사용하면 시간 초과가 납니다. 따라서 한 번의 탐색에 최단 경로와 함께 경로 가중치를 계산해야 합니다.

다익스트라 알고리즘을 계산하는 도중 depth 변수를 추가하여 경로의 개수를 같이 체크 해 둡니다.

depth의 정보를 저장하기 위해 큐를 depth 단계로 나누어 실행해야 하며 같은 depth의 노드들을 모두 탐색한 후 다음 depth로 넘어가야 합니다.

탐색 위치가 목적지가 되면 경로의 비용과 함께 depth를 기록해 둡니다. 

 

탐색이 끝나면 기록해둔 비용과 depth를 검사하면서 최소 비용을 찾아냅니다.

검사 시 인상된 세금을 depth로 곱하여 비용 갱신을 해주며 탐색합니다.

depth 순서대로 탐색하였기 때문에 기록해둔 내용은 depth 순서대로 정렬되어 있으므로 i 번째 값이 현재까지 최솟값보다 크다면 그 정보를 삭제하여도 무방합니다. 이를 통해 세금 인상마다 탐색 횟수를 줄일 수 있습니다.

 

이 상태에서 10만큼 인상하게 되면 최소비용을 갱신하게 되는 (2,100), (2, 80), (3, 50)을 제외한 값들은 모두 삭제하여도 무방합니다. (2, 100), (3, 70), (5, 40)은 다음 세금 인상 시 의미가 없는 값이 되기 때문입니다. 처음부터 순서대로 검사를 하기 때문에 조건 편의상 (2, 100)은 삭제하지 않았습니다.

초기상태

 

10 인상 후 3개의 값이 필요 없어짐

 

 

결과

 

 

코드

#include <cstdio>
#include <queue>
#include <tuple>
#include <vector>
#include <string.h>
using namespace std;
inline void calc(vector<pair<unsigned, unsigned>> &path, int increase) {
    unsigned result = -1;
    for (auto iter = path.begin(); iter != path.end();) {
        iter->second += iter->first*increase;//비용 갱신
        if (result > iter->second) {//최소비용 갱신
            result = result < iter->second ? result : iter->second;
            ++iter;
        }
        else 
            iter = path.erase(iter);    //의미 없는 값 삭제
    }
    printf("%u\n", result);
}
int main() {
    int N, M, K, start, dest;
    unsigned dist[1000], s, e, w;
    vector<pair<unsigned, unsigned>> graph[1000],path;
    queue <pair<unsigned, unsigned>> que;
    scanf("%d%d%d%d%d", &N, &M, &K, &start, &dest);
    start--; dest--;
    memset(dist, -1, N * 4);
    for (int i = 0; i < M; i++) {
        scanf("%u%u%u", &s, &e, &w);
        graph[--s].emplace_back(--e, w);
        graph[e].emplace_back(s, w);
    }
    que.emplace(start, 0);
    unsigned depth = 0;//경로의 개수
    while (!que.empty()) {
        int tmp_size = que.size();
        ++depth;
        while (tmp_size--) {//같은 depth를 한번에 검사
            int cur, cur_cost;
            tie(cur, cur_cost) = que.front();
            que.pop();
            for(auto &t : graph[cur]){
                int next = t.first;
                unsigned next_cost = cur_cost + t.second;
                if (dist[next] > next_cost) {//최소비용이 갱신되는 경우
                    dist[next] = next_cost;
                    if(next == dest)
                        path.emplace_back(depth, next_cost);//목적지에 도달하면 경로 기록
                    que.emplace(next, next_cost);
                }
            }
        }
    }
    calc(path, 0);
    int increase = 0;
    while(K--){
        scanf("%d", &increase);
        calc(path, increase);
    }
}
/*
4 4 2
1 4
1 2 1
1 3 4
2 4 
3 4 2
1
6
*/