[BOJ] 13905 - 세부 (C++, Kruskal,BFS)

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

---

#include <iostream>
#include <string>
#include <queue>
#include <vector>
#include <algorithm>
using namespace std;

#define INF 99999999

struct item{
    int a,b,cost;
};
struct node{
    int e, cost;
};
int n,m;
int s,e;
int parent[100001];
item lst[300001];
vector<node> v[100001];
int visited[100001];

bool compare(item a, item b){
    return a.cost > b.cost;
}
//path compression 미적용
int find(int a){
    if(parent[a] == a) return a;
    return find(parent[a]);
}

void merge(int a, int b){
    a = find(a);
    b = find(b);
    
    //작은 node를 부모로 가지도록 세팅
    //2의 부모는 1이어야 1->2->3 이런식으로 보기좋음
    if(a < b) parent[b] = a;
    else parent[a] = b;
}

bool isSame(int a, int b){
    a = find(a);
    b = find(b);

    if(a==b) return true;
    else return false;
}
/*path compression 적용
int find(int a){
    if(parent[a] == a) return a;
    return parent[a] = find(parent[a]);
}
*/
int main(){
    cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
    cin >> n >> m;
    cin >> s >> e;
    for(int i=0; i<m; i++){
        int a,b,cost;
        cin >> a >> b >> cost;
        lst[i].a = a;
        lst[i].b = b;
        lst[i].cost = cost;
    }
    sort(lst,lst+m, compare);
    for(int i=1; i<=n; i++) parent[i] = i;
    //Kruskal 알고리즘
    //내림차순으로 정렬된 간선과 union 작업
    for(int i=0; i<m; i++){
        int a = lst[i].a;
        int b = lst[i].b;
        int cost = lst[i].cost;

        if(!isSame(a,b)){
            merge(a,b);
            v[a].push_back({b,cost});
            v[b].push_back({a,cost});
        }
    }
    //Kruskal 알고리즘

    //BFS
    queue<int> q;
    q.push(s);
    for(int i=0; i<=n; i++){
        visited[i] = INF;
    }
    while(!q.empty()){
        int current = q.front();
        q.pop();

        for(int i=0; i<v[current].size(); i++){
            int next = v[current][i].e;
            int nextCost = v[current][i].cost;
            if(visited[next] != INF) continue;
            visited[next] = min(nextCost,visited[current]);
            q.push(next);
        }
    }
    //BFS
    if(visited[e] == INF) cout << 0 << endl;
    else cout << visited[e] << endl;
    return 0;
}

문제 접근

DFS로 풀이하면 노드가 너무 많아서 시간초과가 날 것임

-> Union-Find를 이용한 Kruskal 알고리즘을 통해, MST를 이용하자.

문제 실패 원인

1. MST를 반대로(가중치가 최대인 스패닝트리) 구성하고, 그 가중치들의 최솟값을 구하면 되는 줄 알았음.
2. MST를 구성하지 못하는 경우도 있음.

문제 해결 방법

1. BFS를 적용해 그 가중치들 중에서, 목적지에 도달하는 경우의 최솟값을 Visited 배열에 갱신하자
2. 예외처리 하자....
   • 항상 문제에서 '목적지까지 도달하는 경우만 입력으로 주어진다' 혹은 '항상 입력에서는 시작점과 도착점이 다른 경우만 주어진다' 라는 내용이 없다면 다 예외처리 하자.
   • 본 문제에서는 s != e 라는 조건만 주어졌지 그 외의 조건은 주어지지 않았으므로, MST를 구성하지 못하는 경우도 해결해야한다.