백준 1939번:중량제한

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

1939번: 중량제한

이 문제는 이분탐색과 bfs를 쓰면서 풀었다.

이 문제를 보고 처음 든 생각은 시간복잡도 이다.

BFS와 이분탐색이 합쳐져 있기 떄문이다. BFS 시간 복잡도는 O(N) 이고 이분탐색은 O(logn) 즉 합쳐서 O(nlogn)이다.

일단 가중치(무게)를 1부터 최대값을 범위를 지정하고 무게에 따라 이분탐색을 실시했다. 섬이 연결되어 있는 것이라 BFS를 이용해서 섬들을 다 조회해서 정해진 무게랑 비교를 하면서 함수를 작성했다. 코드를 보자 

#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
int start,ed;
vector<pair<int,int>> v[100001];              
bool check[100001];               //섬방문했는지 체크
bool go(int x,int weight){             //weight란 값보다 가지고 갈 수 있는 무게가 더 크면 true반환
    if(check[x]){
        return false;
    }
    check[x]=true;
    if(x==ed){
        return true;
    }
    int len=v[x].size();
    for(int i=0;i<len;i++){
        int next=v[x][i].first;
        int cnt=v[x][i].second;
        if(cnt>=weight){
            if(go(next,weight)){
                return true;
            }
        }
    }
    return false;

}
int main(){
    cin.tie(NULL);
	cout.tie(NULL);
	ios_base::sync_with_stdio(false);
    int n,m;
    cin>>n>>m;  
    while(m--){
        int a,b,c;
        cin>>a>>b>>c;
        v[a].push_back(make_pair(b,c));
        v[b].push_back(make_pair(a,c));
    }
    cin >>start>>ed;
    int left=1;
    int right=1000000000;
    int ans=0;
    while(left<=right){                         //이분탐색
        int mid = left+(right-left)/2;
        memset(check,false,sizeof(check));
        if(go(start,mid)){
            ans=mid;
            left=mid+1;
        }
        else{
            right=mid-1;
        }
    }
    cout<<ans;

}