BOJ 1162 : 도로포장

1162번: 도로포장 (acmicpc.net)

1162번: 도로포장

 

 

 

3줄요약

다익스트라
dp
혼종

 

 

 

서론

 

일반적인 최단거리를 구하는 문제가 아닌, 최단거리를 구하되, K (K <= 20) 개의 도로를 포장하면 그 도로의 길이가 0이 될 때, 최단거리를 구하는 문제이다. 이를 구하기 위해 먼제 3가지 생각이 떠올랐다.

1. 최단거리 알고리즘: 최단거리 알고리즘은 알다시피 3가지가 있다. 하지만 M이 50000이라, 플로이드, 벨만포드는 사용하지 못한고, O(NlogN)의 다익스트라만 사용할 수 있다.
2. 그리디 알고리즘: 두 번째로 그리디이다. 다익스트라로 최단거리를 구한 후, K개만큼 도로를 빼는 것이다. 하지만 반례가 5초만에 생각나 무산되고 말았다.
3. DP: 마지막으로 DP이다. DP가 생각나자마자 "아 이거다" 라는 생각을 하였다. 나는 바로 계획을 실행에 옮겼다.

 

 

 

 

본론

 

풀이

|  다익스트라를 사용하는 동시에 K를 인용한다.

 

1. ( cost, node, 현재까지 포장한 도로 = nodek ) 을 담을 최소 힙을 생성한다.

1-1. dp[i][j] = i 도로까지 j번 포장할 때 최솟값을 저장할 dp배열을 만든다.

2. 최소 힙을 초기화하고 반복한다:

2-1. 만약 dp[node][nodek] 이 cost보다 크면, 즉, 이미 있는 값이 더 크면 continue

2-2. 모든 간선에 대해 반복한다:

2-2-1. nxt = graph[node][i] (다음 노드), nxtd = 다음 노드까지 거리 일때,

2-2-2. 만약 dp[nxt][nodek]이 nxtd보다 클 때, 즉, 포장안할 때에서 갱신하는게 더 이득일 때, 새로 갱신하고 pq에 푸시한다. (chk 대신 이 방식을 선호)

2-2-3. 만약 nodek < K이고, (K일 때 갱신하면 안됨) dp[node][nodek] < dp[nxt][nodek + 1] 일 때, 즉, 포장할 때에서 갱신하는게 더 이득일 때, 새로 갱신하고 pq에 푸시한다.

3. dp[N] 중 가장 최솟값을 찾고, 출력한다.

 

10,000 * 1,000,000 < INT_MAX 인 점을 유의한다.

 

자세한 내용은 코드를 참고

 

#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;
#define ll long long
#define pp pair<int, int>
#define tp pair<ll, pp>
#define INF 87654321234567890

ll dp[10001][21];
int N, M, K;
vector<pair<ll, int> > graph[10001];

int main() {

    scanf("%d %d %d", &N, &M, &K);
    for (int i = 0; i < M; i++) {
        int from, to;
        ll cost;
        scanf("%d %d %lld", &from, &to, &cost);
        graph[from].push_back(make_pair(cost, to));
        graph[to].push_back(make_pair(cost, from));
    }
	
    // 1-1
    for (int i = 1; i <= N; i++) {
        for (int j = 0; j <= K; j++) {
            dp[i][j] = INF;
        }
    }
    dp[1][0] = 0;
	
    // 1
    priority_queue<tp, vector<tp>, greater<tp> > pq;
    pq.push(make_pair(0, make_pair(1, 0)));

    while (!pq.empty()) {
		
        // 2-1.
        ll cost = pq.top().first;
        int node = pq.top().second.first;
        int nodek = pq.top().second.second;

        pq.pop();

        if (dp[node][nodek] < cost) continue; // 2-1

        for (int i = 0; i < graph[node].size(); i++) { // 2-2
        
        	// 2-2-1
            int nxt = graph[node][i].second;
            ll nxtd = graph[node][i].first + dp[node][nodek];

            if (dp[nxt][nodek] > nxtd) { // 2-2-2
                dp[nxt][nodek] = nxtd;
                pq.push(make_pair(nxtd, make_pair(nxt, nodek)));
            }
            if (nodek < K && dp[node][nodek] < dp[nxt][nodek + 1]) { // 2-2-3
                dp[nxt][nodek + 1] = dp[node][nodek];
                pq.push(make_pair(cost, make_pair(nxt, nodek + 1)));
            }
        }
    }

    ll mini = INF;
    for (int i = 0; i <= K; i++) { // 3
        mini = min(mini, dp[N][i]);
    }

    printf("%lld", mini);
}

 

결론

사실 이 문제는 dp문제보다 그래프와 dp를 어떻게 섞고 문제를 풀이해 나갈지를 고민하는 문제이다. dp식을 세우는 문제가 아닌 dp를 구현하는 쪽의 문제라고 생각한다.

난이도(개인적): Gold II

난이도(객관적): Gold I

 

다음 풀 문제: https://www.acmicpc.net/problem/24729 (Gold I)
Or... 2618번: 경찰차 (acmicpc.net) (Platinum V)

 

Contact: How2Contact (tistory.com)

How2Contact