[BOJ] 알고리즘 스터디 boj 1939 중량제한 BFS + BINARY SEARCH

이번에는 백준 1939 중량 제한을 풀어보자

BFS + 이진탐색 으로 풀어야한다.

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

중량제한 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	6701	1657	1016	24.847%

문제

N(2≤N≤10,000)개의 섬으로 이루어진 나라가 있다. 이들 중 몇 개의 섬 사이에는 다리가 설치되어 있어서 차들이 다닐 수 있다.

영식 중공업에서는 두 개의 섬에 공장을 세워 두고 물품을 생산하는 일을 하고 있다. 물품을 생산하다 보면 공장에서 다른 공장으로 생산 중이던 물품을 수송해야 할 일이 생기곤 한다. 그런데 각각의 다리마다 중량제한이 있기 때문에 무턱대고 물품을 옮길 순 없다. 만약 중량제한을 초과하는 양의 물품이 다리를 지나게 되면 다리가 무너지게 된다.

한 번의 이동에서 옮길 수 있는 물품들의 중량의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N, M(1≤M≤100,000)이 주어진다. 다음 M개의 줄에는 다리에 대한 정보를 나타내는 세 정수 A, B(1≤A, B≤N), C(1≤C≤1,000,000,000)가 주어진다. 이는 A번 섬과 B번 섬 사이에 중량제한이 C인 다리가 존재한다는 의미이다. 서로 같은 두 도시 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 두 섬을 연결하는 경로는 항상 존재하는 데이터만 입력으로 주어진다.

출력

첫째 줄에 답을 출력한다.

처음에 이진탐색을 어디에 사용해야할지 몰라서, 문제를 풀지 못했다.

문제 해석을 제대로 하지 못했다. 

옮길 중량을 찾아야 하는데, 섬에 연결된 다리의 제한을 가지고 풀어보려다가 실패했다.

입력받은 다리의 제한들을 이용하여, 처음 출발할 중량을 이진탐색으로 찾으면 됬었다. 

https://ko.wikipedia.org/wiki/이진_검색_알고리즘

이진 검색 알고리즘

위키백과, 우리 모두의 백과사전.

둘러보기로 가기검색하러 가기

이진 검색 알고리즘(binary search algorithm)은 오름차순으로 정렬된 리스트에서 특정한 값의 위치를 찾는 알고리즘이다. 처음 중간의 값을 임의의 값으로 선택하여, 그 값과 찾고자 하는 값의 크고 작음을 비교하는 방식을 채택하고 있다. 처음 선택한 중앙값이 만약 찾는 값보다 크면 그 값은 새로운 최댓값이 되며, 작으면 그 값은 새로운 최솟값이 된다. 검색 원리상 정렬된 리스트에만 사용할 수 있다는 단점이 있지만, 검색이 반복될 때마다 목표값을 찾을 확률은 두 배가 되므로 속도가 빠르다는 장점이 있다.

Binary Search !

정답 소스 코드 :

#include <iostream>
#include <queue>
#include <utility>
#include <memory.h>
#include <cstdio>
using namespace std;
int N,M,a,b,c,maxVal=-1,start,des,answer = -1;
int visited[10001];
typedef pair < int, int > pi;
queue < pi > que;
vector < pi > vc[10001];
 
 
// 중량을 탐색할 BFS 함수
int bfs(int weight){
    que.push({weight,start});
    visited[start] = 1;
    while(!que.empty()){
        int val = que.front().first;
        int cur = que.front().second;
        que.pop();
        
        for(int i=0; i<vc[cur].size(); i++){
            int nVal = vc[cur].at(i).first;
            int next = vc[cur].at(i).second;
            if(val > nVal) continue;
            if(visited[next] == 1) continue;
            visited[next] = 1;
            que.push({val, next});
            if(next == des){
                return val;
            }
        }
    }
    return -1;
}
 
//중량을 검색할 이진탐색 함수
void bs(){
    int mid, begin, last, tmp;
    begin = 0;
    last = maxVal;
    while(begin<=last){
        mid = (begin + last) / 2;
        while(!que.empty()){
            que.pop();
        }
        memset(visited, 0, sizeof(visited));
        tmp = bfs(mid);
        if(tmp == -1){
            last = mid-1;
        }else{
            if(tmp > answer)
                answer = tmp;
            begin = mid+1;
        }
    }
    return;
}
 
int main(){
    scanf("%d %d", &N, &M);
    for(int i=0; i<M; i++){
        scanf("%d %d %d", &a, &b, &c);
        vc[a].push_back({c,b});
        vc[b].push_back({c,a});
        if(c>maxVal)
            maxVal = c;
    }
    scanf("%d %d", &start, &des);
    bs();
    printf("%d\n" , answer);
    return 0;
}
 

함수로 나누지 않으면, 이진탐색과 BFS 시에 처리를 어떻게 해줘야 할지 몰라서 ( 조금 더 복잡해지는... 듯 해서 )

새로 코딩했다.