[이진탐색/BFS] BAEKJOON '1939'번 '중량제한' 문제 (C++/python)

문제 : www.acmicpc.net/problem/1939

1939번: 중량제한

 

 

 

• 문제 해결 아이디어

    1.  중량제한 C의 범위가 10억이므로, 이진탐색을 사용하여 중량의 최대값을 구한다.

   

    2.  해당 중량을 목적지까지 옮길 수 있는지 여부는 BFS를 통해 판단한다.

 

 

 

 

예제입력

3 3
1 2 2
3 1 3
2 3 2
1 3

 

 

 

다음 입력이 주어졌다면, 1이 시작점 3이 끝점으로 하여

다음과 같이 그릴 수 있다.

 

 

 

현재 최대 무게가 2( middle_weight )라 할 때, BFS로 1에서 3까지 가는 경로가 있음을 확인할 수 있으므로 result에 middle_weight를 넣어준다. 이후 min_weight를 middle_weight보다 1 증가시켜준다.(현재 무게보다 더 무거워져도 이동할 수 있는지 확인하기 위해서)

 

 

 

 

 

현재 최대 무게가 3(middle_weight)이라 할 때, BFS로 1에서 3까지 가는 경로가 있음을 확인할 수 있으므로 result에 middle_weight를 넣어준다. 이후 min_weight를 middle_weight보다 1 증가시켜주면 min이 max보다 커지므로, 과정을 끝내고 result를 출력한다.

 

 

• python

 

from collections import deque

n, m = map(int, input().split())
edges = [[] for _ in range(n+1)]

def bfs(c):
    queue = deque([start])
    check = [False] * (n+1)
    check[start] = True
    while queue:
        now = queue.popleft()
        for next, weight in edges[now]:
            if not check[next] and weight >= c:
                check[next] = True
                queue.append(next)
    return check[end]


max_weight = 1
min_weight = 1000000000

for _ in range(m):
    node1, node2, weight = map(int,input().split())
    edges[node1].append((node2, weight))
    edges[node2].append((node1, weight))
    max_weight = max(max_weight, weight)
    min_weight = min(min_weight, weight)

start, end = map(int, input().split())

result = min_weight
while(min_weight <= max_weight):
    middle_weight = (min_weight + max_weight) // 2
    if bfs(middle_weight):
        result = middle_weight
        min_weight = middle_weight + 1
    else:
        max_weight = middle_weight - 1

print(result)

 

 

• c++

#include <iostream>
#include <vector>
#include <queue>
#define node_max 10001
#define max 1000000001

using namespace std;

vector<pair<int,int>> edges[node_max]; // first : node, second : weight
int n;


bool bfs(int start, int end, int input_weight){
    queue<int> q;
    q.push(start);
    
    bool check[n+1];
    fill(check,check+n+1,false);       // 단순 반복문으로 작동 O(N)
    
    while(!q.empty()){
        int now = q.front();
        q.pop();
        check[now] = true;
        
        for(int i= 0 ; i< edges[now].size(); i++){
            int next_weight = edges[now][i].second;
            
            if(!check[edges[now][i].first] && next_weight >= input_weight){
                q.push(edges[now][i].first);
                check[edges[now][i].first] = true;
            }
        }
    }
    return check[end];
    
}



int main(){
    
    int m, result=0;
    int max_weight= 0, min_weight= max;
    
    scanf("%d %d",&n,&m);
    
    for(int i=1 ; i<= n ; i++){
        edges[i].clear();
    }
    
    for(int i=0 ; i< m ; i++){
        int node1, node2, weight;
        scanf("%d %d %d",&node1, &node2, &weight);
        
        if(weight > max_weight)
            max_weight = weight;
        if(weight < min_weight)
            min_weight = weight;
        
        edges[node1].push_back(make_pair(node2,weight));
        edges[node2].push_back(make_pair(node1,weight));
    }
    
    int start,end;
    scanf("%d %d",&start, &end);
    
    while(min_weight <= max_weight){
        int middle_weight = (min_weight + max_weight)/ 2;
        
        if(bfs(start, end, middle_weight)){
            result = middle_weight;
            min_weight = middle_weight+1;
        }
        
        else{
            max_weight = middle_weight-1;
        }
    }
    printf("%d\n",result);
    
    return 0;
}