[백준][1939번][이분탐색] 중량제한

중량제한

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

<코드>

#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
 
vector<pair<int, int>> bridge[100010];
int visit[100010] = {};
 
bool finalmap(int vertx, int weight,int finalvertx){
    bool result = false;
    
    if (finalvertx == vertx)
        return true;
 
    for (int i = 0; i < bridge[vertx].size(); i++){
        if (visit[bridge[vertx][i].first] == 0 && weight <= bridge[vertx][i].second){
            visit[bridge[vertx][i].first] = 1;
            result = finalmap(bridge[vertx][i].first, weight, finalvertx);
 
            if (result)
                return true;
        }
    }
    return result;
}
 
 
int main(void){
 
    int N, M;
    //처음int는 다음 정점 마지막 int 값어치
 
    int weight[100010];
 
    int result;
    int start, end;
    scanf("%d %d", &N, &M);
    
    for (int i = 0; i < M; i++){
        int A, B, C;
        scanf("%d %d %d ", &A, &B, &C);
        bridge[A].push_back(make_pair(B, C));
        bridge[B].push_back(make_pair(A, C));
        weight[i] = C;
    }
    
    scanf("%d %d", &start, &end);
    sort(weight, weight + M);
    
    int left = 0, right = M - 1; 
 
 
    while (left <= right){
        visit[start] = 1;
 
        int mid = (left + right) / 2;
        if (finalmap(start, weight[mid], end))
        {
            result = weight[mid];
            left = mid + 1;
        }
        else
            right = mid - 1;
 
        for (int i = 1; i <= M; i++)
            visit[i] = 0;
 
    }
 
    printf("%d\n", result);
 
    return 0;
}

<문제 푼 요령>

 1. 이분탐색을 이용하였다.

 2. 문제 -> 정답을 구하는 과정이 아닌 정답을 유추 -> 문제에 대입으로 풀었다 이 정답을 유추하는 과정에서 이분탐색을 사용하였다.

 3. 다리의 중량제한 값을 따로 배열을 만든 뒤 정렬한 뒤에 이 중에서 분명 답이 있기 때문에 이분탐색으로 최적의 값을 구하였다.

 4. 각각의 정답 -> 문제에 대해서는 시작점에서 유추한 중량을 가진 트럭이 출발해서 끝점까지 도착할 수 있는지 없는지만 보았다.

 5. 여기서 도착할 수 있다면 이 도착할 수 있는 값을 저장해 놓고 이 중량보다 위의값을 다시 검색하는 순서로 진행하였다.

 6. 즉 최종값에서 가장 중량이 높으면서 출발점에서 끝점까지 도착만 할 수 있다면 그 값이 정답이 되는것이다.