[백준][C++] 1800 인터넷 설치

www.acmicpc.net/problem/1800

1800번: 인터넷 설치

 

 

알고리즘 종류

    - 다익스트라

    - 이분탐색

 

 

 

사고 과정

    1. 이분탐색을 통해서 '목표 최소 비용'을 결정한다.

    2. 결정한 최소비용을 가지고 다익스트라 알고리즘을 수행한다.

        2-1. 최소비용만 저장하는 배열에는 '목표 최소 비용'보다 큰 지 작은 지에 따라 값을 저장한다. 예시를 보면, 1에서 5까지 가는 동안 4 -> 3 -> 9를 거친다. 이때 목표 최소 비용이 4이면 0+0+1이 배열에 저장된다. 

        2-2. 다익스트라가 끝나면, 배열의 n번째에 k보다 같거나 작은 값이 저장되어 있는지 확인한다. k보다 같거나 작다는 것은 무료로 설치하는 케이블을 맞추면서 최소 비용('목표 최소 비용')을 지불할 수 있다는 말이다.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <queue>
#define MAX 987654321
 
using namespace std;
 
int n, p, k;
int answer = MAX;
 
vector<vector<pair<int, int> > > edges;
int minPassed[1001];
 
bool dijkstra(int target){
    
    for(int i=1; i<=n; i++) minPassed[i] = MAX;
    
    priority_queue<pair<int, int> > pq;
    pq.push({0, 1});
    minPassed[1] = 0;
    
    while(!pq.empty()){
        
        int here = pq.top().second;
        int passed = -pq.top().first;
        pq.pop();
        
        if(minPassed[here] > passed) continue;
        
        for(int i=0; i<edges[here].size(); i++){
            int next = edges[here][i].first;
            int next_passed = passed + (edges[here][i].second > target);
            
            if(next_passed < minPassed[next]){
                minPassed[next] = next_passed;
                pq.push({-next_passed, next});
            }
        }
    }
 
    return minPassed[n] <= k;    
}
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    
    cin >> n >> p >> k;
    edges.resize(n+1);
    
    int u, v, c;
    int maxNum=0;
    for(int i=0; i<p; i++){
        cin >> u >> v >> c;
        edges[u].push_back({v, c});
        edges[v].push_back({u, c});
        maxNum = max(maxNum, c);
    }
    
    
    int left=0, right=maxNum, mid;
    while(left<=right){
        mid = (left+right)/2;
        if(dijkstra(mid)){
            right = mid - 1;
            answer = mid;
        }
        else{
            left = mid + 1;
        }
    }
    
    if(answer == MAX) cout << -1;
    else cout << answer;
}
 

 

 

 

시행착오

    - 이 분의 블로그에서 도움을 받았다.

    - 이 문제의 핵심은 다익스트라를 수행할 때, 배열에 비용들의 합을 저장하는 것이 아닌 '목표 최소 비용'을 통과할 수 있는지 없는지를 저장하는 것이다. 통과할 수 있으면 0, 통과할 수 없으면 1을 추가한다. 그리고 '목표 최소 비용'은 이분탐색을 통해서 구할 수 있다.

    - 문제를 분석하면서, 다익스트라와 이분탐색을 생각하지 못한 것은 아니었다. 그런데 이 둘의 융합이라는 단계로 생각이 확장되지 못했다. 

    - 어려운 문제를 풀수록 배우는 것이 많은 것 같다. 힘드러라도 어려운 문제를 풀어야 할 것이다.