[백준][C++] 1939번: 중량제한 <183>

직접 풀어보고 올리는 코드입니다. 지적이나 더 좋은 방향에 대한 댓글은 항상 환영합니다.

1939번: 중량제한

 

생각의 흐름

이번 문제는 BFS + 이분탐색(파라메트릭 서치) 가 포함된 문제이다.

 

이분탐색은 가능한 범위 내에서 탐색을 해야 한다.

답으로 가능한 가장 작은 중량제한은 0 부터 ~ 가장 무거운 중량제한은 입력으로 받은 다리의 중량 최대값이다.

 

예를 들어 m이라는 값이 이번에 확인할 중량이라 해보자.

시작지점 에서부터 도착지점 까지 중량 제한 m으로 운반 가능한지를 확인하면 됩니다!

 

다음과 같은 알고리즘으로 진행하게 됩니다.

1, 입력 받은 중량 중 하나가 답이므로 low = 0, high = 최대 중량 으로 초기화하여 탐색을 시작합니다.

2. 중량제한이 mid일 때 BFS 함수를 호출해서 시작섬에서 도착섬까지 운반 가능하면 low를 업데이트하고 운반할 수 없다면 high를 업데이트합니다.

3. 최대 중량은 high이므로 이진탐색이 끝나면 high를 출력합니다.

 

나의 코드

#include <bits/stdc++.h>
using namespace std;
#define MAX 100001

int N, M;
int start, finish;
vector<pair<int, int>> adj[MAX];
bool visited[MAX];

bool BFS(int cost){
    queue<int> Q;
    Q.push(start);
    visited[start] = true;

    while(!Q.empty()){
        int now = Q.front();
        Q.pop();

        if(now == finish){
            return true;
        }

        for(int i = 0; i < adj[now].size(); i++){
            int nextPosition = adj[now][i].second;
            int weight = adj[now][i].first;
	// 내가 생각 한 답 cost랑 같거나 더 무거운 것을 버틸수 있다면 && 방문안했다면
            if(weight >= cost && !visited[nextPosition]){
                visited[nextPosition] = true;
                Q.push(nextPosition);
            }
        }
    }

    return false;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;
    int from, to, weight;
    int left = 0, right = 0;
    for(int i = 0; i < M; i++){
        cin >> from >> to >> weight;
        adj[from].push_back({weight, to});
        adj[to].push_back({weight, from});
        right = max(right, weight);
    }
    cin >> start >> finish;

    while(left <= right){
        memset(visited, false, sizeof(visited));

        int mid = (left + right) / 2;
        if(BFS(mid)){
            left = mid+1;
        }else{
            right = mid-1;
        }
    }

    cout << right;

    return 0;
}