[C언어] 백준 13905번 세부

13905번: 세부

 

문제

빼빼로 데이를 맞아 혜빈이와 숭이는 세부에 있는 섬에 놀러 갔다. 섬은 바다 위에 떠다니는 집과 집들을 연결하는 오크나무로 되어있는 다리로 이뤄져 있다. 숭이는 혜빈이에게 깜짝 이벤트를 해주기 위해 섬 관리자에게 혜빈이를 이벤트장소에 머물게 해달라고 하였다. 이벤트 당일 날 숭이는 금으로 된 빼빼로들을 들고 이벤트 장소로 이동하려 했다. 하지만 아뿔싸! 각 다리마다 다리 위를 지날 수 있는 무게 제한이 존재했다. 비싼 금빼빼로를 가면서 버리기 아깝던 숭이는 자신이 머물던 집에서 자신이 혜빈이에게 갈 수 있는 최대한의 금빼빼로만을 들고 가려고 한다. 따라서 숭이는 인공위성조차 해킹할 수 있는 당신에게 혜빈이에게 들고 갈 수 있는 최대한의 금빼빼로 개수를 알려달라고 부탁했다. 당신은 인공위성을 해킹하여 집들의 번호와 다리의 무게제한을 알아내었다. 이 정보를 가지고 빨리 숭이를 도와주자.

(금빼빼로 하나의 무게는 1이고, 숭이의 몸무게는 고려하지 않는다.)

입력

첫 번째 줄에는 섬에 존재하는 집의 수 N(2≤N≤100,000)와 다리의 수 M(1≤M≤300,000)이 주어진다. 두 번째 줄에는 숭이의 출발 위치(s)와 혜빈이의 위치(e)가 주어진다. (1≤s, e≤N, s≠e). 다음 M개의 줄에는 다리의 정보가 주어진다. 각 줄은 “집의 번호 h1(1≤h1≤N), 집의 번호 h2(1≤h2≤N), 다리의 무게제한 k(1≤k≤1,000,000)” 형식으로 주어진다. (h1집과 h2집은 무게제한이 k인 다리로 연결되어 있다.)

출력

숭이의 출발위치에서 혜빈이의 위치까지 숭이가 들고 갈 수 있는 금빼빼로의 최대 개수를 출력하시오.

코드

#include <stdio.h>
#include <stdlib.h>

typedef struct{
    int start;
    int end;
    int max_w;
}lst;

// 내림차순 정렬
int cmp(const void *a, const void *b){
    lst *pa = (lst *)a;
    lst *pb = (lst *)b;
    if(pa->max_w > pb->max_w) return -1;
    else if(pa->max_w == pb->max_w) return 0;
    else return 1;
}

int find_parent(int x, int parent[]){
    if(parent[x] != x)
        parent[x] = find_parent(parent[x], parent);
    return parent[x];
}

void union_parent(int a, int b, int parent[]){
    a = find_parent(a, parent);
    b = find_parent(b, parent);

    if(a == b) return;

    if(a < b){
        parent[b] = a;
    }else{
        parent[a] = b;
    }
}


int main(){
    int n, m, s, e;
    int h1, h2, k;
    scanf("%d %d", &n, &m);
    scanf("%d %d", &s, &e);
    lst* arr = (lst *)malloc(sizeof(lst)*m);
    for(int i=0;i<m;i++){
        scanf("%d %d %d", &arr[i].start, &arr[i].end, &arr[i].max_w);
    }

    int *parent = (int *)malloc(sizeof(int)*(n+1));
    for(int i=1;i<n+1;i++){
        parent[i] = i;
    }

    // 정렬
    qsort(arr, m, sizeof(lst), cmp);

    // Kruskal
    int ans = 0;
    for(int i=0;i<m;i++){
        union_parent(arr[i].start, arr[i].end, parent);
        if(find_parent(s, parent) == find_parent(e, parent)){
            ans = arr[i].max_w;
            break;
        }
    }
    printf("%d", ans);

    free(arr);
    free(parent);

    return 0;
}

최대한 많은 빼빼로를 들고 가려면 무게제한이 큰 다리부터 사용하도록 MST를 만들어야 한다. 그러므로 우선 무게제한을 기준으로 내림차순 정렬해준다. 정렬된 배열의 앞에서부터 다리를 선택하여 s와 e가 연결된 것을 확인하면 멈추고 그 때의 무게 제한을 ans에 저장해준다.

어떤 두 정점이 같은 트리에 포함되었는지 확인하려면 루트 정점이 같은지 확인해주면 된다.

 

처음에는 ans에 저장하지 않고 바로 출력되게 해주었는데 틀렸다. s와 e가 연결될 수 없는 경우도 존재하는 것 같다. 그래서 바로 출력하지 않고 ans에 저장해두었다가 출력되게 하였다. ans의 초기값은 0이기 때문에 연결되지 않는다면 0이 출력될 것이다.