[백준][C++] 13905 세부

www.acmicpc.net/problem/13905

13905번: 세부

 

 

 

알고리즘 종류

    - 이분탐색

    - MST

 

 

 

사고 과정

    1. 최대 스패닝 트리를 만든다.

    2. BFS로 시작점에서 출발하여 도착지점에 도달할 때까지 각 간선의 최소값만 저장한다.

 

 

 

구현(C++)

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
 
using namespace std;
 
int n, m;
int s, e;
 
vector<pair<pair<int, int>, int> > edges;
vector<int> parents;
vector<vector<pair<int, int> > > graph;
 
 
bool cmp(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b){
    return a.second > b.second;
}
 
int get_parent(int a){
    if(parents[a] == a) return a;
    return parents[a] = get_parent(parents[a]);
}
 
void union_parents(int a, int b){
    
    a = get_parent(a);
    b = get_parent(b);
    
    if(a>b) parents[a] = b;
    else parents[b] = a;
}
 
void kruskal(){
    
    for(int i=1; i<=n; i++) parents[i] = i;
    sort(edges.begin(), edges.end(), cmp);
    
    for(int i=0; i<edges.size(); i++){
        if(get_parent(edges[i].first.first) != get_parent(edges[i].first.second)){
            
            union_parents(edges[i].first.first, edges[i].first.second);
            
            // 최대값으로 연결된 스패닝 트리  
            graph[edges[i].first.first].push_back({edges[i].first.second, edges[i].second});
            graph[edges[i].first.second].push_back({edges[i].first.first, edges[i].second});
        }
    }
}
 
// 최대값 스패닝 트리에서 BFS로 탐색하여 최소값만 저장하기
// DP처럼 이전 값과 현재 값을 비교하여 최소값만 저장  
void find_path(){
    vector<int> costs;
    vector<int> isVisited;
    isVisited.resize(n+1);
    costs.resize(n+1);
    for(int i=1; i<=n; i++) costs[i] = 987654321;
    
    queue<int> q;
    q.push(s);
    isVisited[s] = 1;
    costs[s] = 987654321;
    
    while(!q.empty()){
        int here = q.front();
        q.pop();
        
        for(int i=0; i<graph[here].size(); i++){
            int next = graph[here][i].first;
            int next_cost = graph[here][i].second;
            
            if(isVisited[next]) continue;
            isVisited[next] = 1;
            
            costs[next] = min(costs[here], next_cost);
            q.push(next);
        }
    }
    
    // 못 갈 수도 있는 경우 고려해야 한다. 
    if(costs[e] == 987654321) cout << 0 << "\n";
    else cout << costs[e] << "\n";
}
 
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    
    cin >> n >> m;
    cin >> s >> e;
    
    parents.resize(n+1);
    graph.resize(n+1);
    
    int u, v, c;
    for(int i=0; i<m; i++){
        cin >> u >> v >> c;
        edges.push_back({{u, v}, c});
    }
    
    kruskal();
    find_path();
}

 

 

 

시행착오

    - 처음에 그래프를 보고 다익스트라를 사용할 지 고민했다. 왜냐하면, 출발지와 목적지가 분명하고 최소비용을 출력하기 때문이다. 그런데 할 수 없었다. 왜냐하면, 출발지에서 시작하여 목적지까지 최소 경로가 본인이 원하는 경로가 아닐 수 있다. 무슨 말이냐면, 1->5까지에서 최소 빼빼로를 다익스트라로 하면 1이 나올 것이다(어떻게 설계하느냐에 따라 다르겠지만 본인의 한계는 여기까지) 따라서 우선, 정제된 그래프가 필요하다고 생각했다. 그래서 최대 스패닝 트리를 먼저 수행하고 다익스트라(BFS)를 수행하기로 했다.

 

    - 어느 분들은 이분탐색을 진행하셨다. 굉장히 새로웠다. 빼빼로의 최대 갯수를 target으로 정해서 BFS를 수행하고 만약에 목적지에 도달했으면, 빼빼로의 최대 갯수를 늘린다.