[ BOJ 백준 11085번 - 군사 이동 ] 해설 및 코드

 

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

목적

Baekjoon World의 수도 c에서 Cube World의 수도 v로 가는 어떤 경로에서, 가장 작은 길의 너비를 x라고 할 때, 이 x가 가장 큰 경로를 찾자.

 

접근법

1. 탐욕적으로 해결한다. w개의 길을 너비 순으로 정렬하여, 큰 너비부터 해당 길의 양 지점을 잇는다. 즉, Disjoint-set을 이용하여 한 집합으로 병합한다.

2. 매번 이 과정을 진행하면서, c와 v가 한 집합에 있는지 확인한다.

3. 다른 방법으로는, BFS을 이용하여 역시 탐욕적으로 큰 너비의 길부터 이어나가면서, 이를 v에 도달할 때까지 반복하여 해결할 수도 있다.

 

#include<bits/stdc++.h>
#define f(i,l,r) for(int i=l;i<r;i++)
using namespace std;
 
int s[1000];
struct info{
    int x,y,z;
    bool operator<(const info& oth)const{return z>oth.z;}
}a[50000];
 
int find(int x){
    return s[x]<0?x:s[x]=find(s[x]);
}
 
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    
    memset(s,-1,sizeof(s));
    int p,w,c,v;cin>>p>>w>>c>>v;
    f(i,0,w)cin>>a[i].x>>a[i].y>>a[i].z;
    
    sort(a,a+w);
    f(i,0,w){
        int x=find(a[i].x),y=find(a[i].y);
        if(x!=y){
            s[y]=x;
            if(find(c)==find(v)){
                cout<<a[i].z;
                break;
            }
        }
    }
    
    return 0;
}
 

 

문제 설명과 코드에 대한 피드백은 언제나 환영합니다.

 다양한 의견 댓글로 남겨주세요.