백준 1939 중량제한

문제링크 : https://www.acmicpc.net/problem/1939

아이디어

• 접근 1. BFS로 두 섬을 잇는 경로 확인
  • 근데 BFS를 통해 최대값 구하기? > 불가능
• 접근 2. 최소값이므로, 다익스트라?
  • 다익스트라는 간선의 가중치가 주어질떄 최소 거리를 구하는 문제
  • 이 문제는 연결할 수 있는 최대값을 구하는 문제이므로 불가능
• 접근 3. 이진탐색으로 중량의 최대값을 구하기
  • 중량이 정해지면 BFS로 건널수 있는지 확인

시간복잡도 계산

• 중량의 최대값 구하기 : lgC
  • BFS로 건널수 있는지 확인
    • BFS : O(V+E)
    • V : N
    • E : 2M (다리가 양방향이므로 2배)
    • O(V+E) = O(N + 2M) = O(N)
• 총합 : O(lgC * N)
  • N : 1e5
  • lgC : 30
  • 총합 : 3e6 > 가능

자료구조

• BFS 사용할 인접리스트 vector<pair<int, int>>
  • 거리는 최대 1e9이므로 INT 가능

코드(C++)

#include <iostream>
#include <queue>
#include <vector>
 
using namespace std;
 
vector<pair<int, int>> adj[100010];
int st,en;
 
bool bfs(int num) {
    bool chk[100010];
    fill(chk, chk+100010, 0);
    
    queue<int> q;
    q.push(st);
    chk[st] = 1;
    
    while(!q.empty()) {
        int eq = q.front(); q.pop();
        if(eq==en) return 1;
        
        for(auto x : adj[eq]) {
            int ec = x.first;
            int ei = x.second;
            
            if(ec < num) continue;
            if(chk[ei]) continue;
            
            chk[ei] = 1;
            q.push(ei);
        }
        
    }
    
    return 0;
    
}
int binsearch(int st, int en) {
    if(st==en) {
        return st;
    }
 
    // 여기서 내림을 하게되면, 가능한 수중 가장 낮은 값을 찾게됨
    // 그래서 올림을해줘야 가능한수 중 가장 높은값을 찾음
    int mid = (st+en+1)/2;
    if(bfs(mid) == true) return binsearch(mid, en);
    else return binsearch(st, mid-1) ;
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int N,M; cin >> N >> M;
    for(int i=0; i<M; i++) {
        int a,b,c; cin >> a >> b >> c;
        adj[a].push_back(make_pair(c,b));
        adj[b].push_back(make_pair(c,a));
    }
    
    cin >> st >> en;
    
    cout << binsearch(1,1e9) << '\n';
    return 0;
}
 
 

문제유형

• 이진탐색 - 케이스를 이분탐색

비슷한 문제

• https://www.acmicpc.net/problem/1300
• https://www.acmicpc.net/problem/1939
• https://www.acmicpc.net/problem/2805
• https://www.acmicpc.net/problem/1654