[ 백준 1939 ] 중량제한 (C++)

백준의 중량제한(1939) 문제이다.

( 문제 바로가기 )

[ 문제풀이 ]

1) 어렵지 않은 문제 였지만, 시간초과 때문에 생각을 조금 더 해봐야 하는 문제이다. 시간초과를 막기 위해서 이분탐색과

   BFS를 이용해서 풀었다.

   먼저 이분탐색에 대해서 간단하게 알아보자. 이분탐색은 탐색 범위를 2개의 범위로 나누어서 탐색하는 방법으로 일반적으로

   Left와 Right 혹은 Low와 High값으로 최소 최대값을 나눈 후에, 이 2개의 중간값인 Mid값을 기준으로 탐색을 진행한다.

   만약에 이 Mid값을 기준으로 탐색이 완료된다면, 더 큰 범위의 탐색이 가능하다는 말이므로, Low 혹은 Left의 값을

   Mid+1의 값으로 반대라면, High 혹은 Right의 값을 Mid-1의 값으로 바꿔주면서 탐색을 계속 진행하는 방식이다.

void Binary_Search()
{
    int Left = 0;
    int Right = Max;
 
    while(Left <= Right)
    {
        int Mid = (Left + Right ) / 2;
        
        if(Mid값을 통해서 하고자 하는 작업 == true) Left = Mid + 1;
        else Right = Mid - 1;
    }
}

< 이분탐색의 전체적인 구현 법이다. 절대 정답이 아니고 본인이 주로 사용하는 코딩 방법이다. >

   이분탐색을 진행하기 위해서, 본인은 입력을 받을 때, 중량의 최댓값을 따로 저장해 주었다.

   이 후, Low = 0 , High = 중량의 최댓값 을 통해서 BFS()를 반복 실행시켜 주었다.

 

2) BFS() 에서는 현재 내가 있는 섬에서 다른 섬으로 넘어갈 때, 더 큰 중량을 가져갈 수 있는 섬에 대해서만 Queue에 반복적으

   로 push해주면서 진행하였다.

   진행 도중, 우리가 도착점으로 지점해둔 섬에 도착한다면, true를 그게 아니라면 false를 반환 하는 bool형의 BFS로 구현

   하였고, true가 반환된다면, 더 높은 중량을 기준으로 탐색이 가능하다는 말이므로 Low = Mid + 1 , 반대라면

   High = Mid - 1의 반복을 통해서 답을 도출하였다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
 
#define endl "\n"
#define MAX 100000 + 1
using namespace std;
 
int N, M, Max_Cost, Start, End;
bool Visit[MAX];
vector<pair<int, int>> V[MAX];
 
int Bigger(int A, int B) { if (A > B) return A; return B; }
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < M; i++)
    {
        int Pos1, Pos2, Cost;
        cin >> Pos1 >> Pos2 >> Cost;
        V[Pos1].push_back(make_pair(Pos2, Cost));
        V[Pos2].push_back(make_pair(Pos1, Cost));
        
        Max_Cost = Bigger(Max_Cost, Cost);
    }
 
    cin >> Start >> End;
}
 
bool BFS(int Cur_Cost)
{
    queue<int> Q;
    Q.push(Start);
    Visit[Start] = true;
 
    while (Q.empty() == 0)
    {
        int Cur_Factory = Q.front();
        Q.pop();
 
        if (Cur_Factory == End) return true;
 
        for (int i = 0; i < V[Cur_Factory].size(); i++)
        {
            int Next_Factory = V[Cur_Factory][i].first;
            int Next_Factory_Cost = V[Cur_Factory][i].second;
 
            if (Visit[Next_Factory] == false && Cur_Cost <= Next_Factory_Cost)
            {
                Visit[Next_Factory] = true;
                Q.push(Next_Factory);
            }
        }
    }
    return false;
}
 
void Solution()
{
    int Low = 0;
    int High = Max_Cost;
    while (Low <= High)
    {
        memset(Visit, false, sizeof(Visit));
        int Mid = (Low + High) / 2;
        if (BFS(Mid) == true) Low = Mid + 1;
        else High = Mid - 1;
    }
    cout << High << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}