문제

• n개의 정점과, m 개의 간선이 주어집니다.

• m개의 줄에는 간선의 정보 3정수 a, b, c가 주어집니다. a->b로 가는데 무게 제한이 c라는 의미입니다.

• 무게 제한 c 이하로만 이동할 수 있습니다.

• 모든 간선은 양방향 입니다.

• 마지막 줄에는 출발 정점과, 도착 정점이 주어집니다.

• n, m(1 ≤ n,m ≤ 10만) 정점과 간선의 개수 각각 10만 이하

• 중량의 범위 c (1 ≤ c ≤ 10억)

• 시작점에서 도착점으로 이동할 수 있는 중량의 최대값을 구하세요

• 시간 제한 1초

• 문제 링크

---

접근 과정

1. 이진 탐색

• 1~ 10억 범위를 탐색하기 위해서 이진 탐색을 사용합니다. 10억이기 때문에 for문 한번 수행하는 것만으로도 10초가 걸립니다. 이진 탐색을 사용하면 30번만 수행하면 됩니다.(2^30은 10억이 조금 넘습니다.)

2. BFS, DFS

• 그래프를 탐색하기 위해 DFS, BFS 어느것을 사용해도 상관 없습니다. 시작점에서 출발해서 도착점에 도달 할 수 있는지 여부를 확인하는 용도로 사용합니다.

3. 시간 복잡도 계산

• 1 ~ 10억 범위 이진 탐색 -> (log10억) -> 30
• BFS로 그래프 탐색 (v+e) -> 20만 -> 2n -> 상수생략 n -> 10만
• O(nlogc) -> 30 * 10만 -> 300만 -> 1억이 1초걸리니까 시간안에 충분히 풀 수 있습니다.

코드

1. C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#define max_int 100001
using namespace std;

//시간 복잡도: O(nlogc)
//공간 복잡도: O(n)
//사용한 알고리즘: 이진 탐색, BFS
//사용한 자료구조: 링크드 리스트(vector로 간선 저장)

int n, m, a, b, c, start_node, end_node, max_cost = 0;

// 중량의 최대값을 저장할 변수 result, 최소값 1로 초기화합니다.
int result = 1;

// 정점의 정보를 담을 구조체
struct info{
    int cur;
    int cost;
};

// 간선의 정보를 담을 링크드 리스트
vector<info> v[max_int];

// 정점 도착 여부를 저장하는 체크 배열
bool check[max_int];

// 3. BFS
// 그래프 탐색 O(v+e) -> 상수 생략 O(e)
void bfs(int mid){
    queue<int> q;
    check[start_node] = true;
    q.push(start_node);
    while(!q.empty()){
        int node = q.front();
        q.pop();
        
        for(int i=0; i<v[node].size(); i++){
            info next = v[node][i];
            int n_node = next.cur;
            int n_cost = next.cost;
            
            // 다음 정점을 방문하지 않았고, 중량 제한에 걸리지 않는다면
            if(!check[n_node] && n_cost >= mid){
                check[n_node] = true;
                // 다음 정점으로 이동합니다.
                q.push(n_node);
            }
        }
    }
}

// 4. 도달 여부 반환
// 도착점 도달 여부를 반환합니다.
bool cal_cost (int mid) {
    bfs(mid);
    
    return check[end_node];
}

// 2. 이진 탐색
//  이진 탐색으로 중량 제한 범위 1 ~ 10억에서 중량의 최댓값을 찾습니다. O(log10억)
void binary_search(){
    int start = 1;
    int end = max_cost;
    int mid = 0;
    while(start <= end){
        mid = (start + end) / 2;
        
        // BFS를 위한 체크 배열 초기화
        for(int i=1; i<=n; i++) check[i] = false;
        
        // 도착점에 도달 할 수 있으면, 중량을 높입니다.
        if(cal_cost(mid)){
            result = max(result, mid);
            start = mid + 1;
        // 도착할 수 없으면 중량을 낮춥니다.
        }else{
            end = mid - 1;
        }
    }
}

int main(){
    // 1. 문제를 입력받습니다.
    scanf("%d %d", &n, &m);
    
    // 간선의 정보를 받습니다.
    for(int i=0; i<m; i++){
        scanf("%d %d %d", &a, &b, &c);
        max_cost = max(max_cost, c);
        // 간선의 정보를 받고 양방향 그래프를 만들어줍니다.
        v[a].push_back({b, c});
        v[b].push_back({a, c});
    }
    scanf("%d %d", &start_node, &end_node);
    
    // 2. 이진 탐색을 수행합니다.
    binary_search();
    
    // 5. 결과를 출력해줍니다.
    printf("%d\n", result);
}