[ 백준 13905 ] 세부 (C++)

백준의 세부(13905) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 먼저 문제를 어떤 알고리즘을 사용해야 될 지 부터 생각을 해보자. 가장 처음에 든 생각은 '완전탐색' 이였다.

   하지만, 집의 수가 최대 10만개 이고, 다리의 수는 30만개이다.

   그렇다면, 1번에서 10만번집에 도달을 해야 하는데, '1'번집을 제외한 모든 집들이 서로 모두 연결되어 있는 상황이라고

   생각해보자.

   생각이 안드는게 당연하다. 문제를 작은 숫자로 바꿔서 생각을 해보자.

   집의 최대 수가 6개이고, '1'번에서 '6'번 집으로 가야할 때, '1'번과 '6'번 집을 제외한 모든 집들이 서로 연결되어 있는

   상황이라고 생각해보자. 그림으로 표현하자면 다음과 같다.

  

    위와 같은 상황이라고 생각해보자. 우리는 1번에서 6번으로 도달해야 하는데, 갈 수 있는 경우의 수가 너무나도 많다.

    최악의 경우라고 생각해보면 시작점과 도착점을 제외한 나머지 집들은 N - 1개의 선을 가질 수 있고,

    이는 N - 2개의 집들이(시작 집, 도착 집 제외) N - 1개의 선을 가질 수 있다는 것을 의미한다.

    그렇다면 다시 문제로 돌아와서 보면 집의 갯수가 최대 10만개 이다.

    10만개를 위의 식에 대입해보면, 99998개의 집들이 99999개의 선을 가진다는 것을 의미하고 완전탐색으로 탐색을 한다고

    생각해보면 약 10억번의 탐색이 진행된다. 즉, 제한시간 1초에 통과될 수가 없다.

    따라서, 우리는 완전탐색으로는 진행이 불가능하다.

2) 그래서 본인은 '이분탐색' 법을 사용하였다. 들고 갈 수 있는 최대 금빼빼로의 무게인 백만(100,000,0)을 High값으로

   0을 Low값으로 두고, 이분탐색을 진행하였다.

   즉, 쉽게 말하자면 '들고 갈 무게를 미리 정해놓고 움직여 보았다 !' 라고 생각할 수 있다.

   구체적인 구현 방법은 다음과 같다. BFS + 이분탐색을 이용하였는데, 이분탐색을 통해서 들고갈 무게가 정해지면

   그 무게를 가지고 BFS를 통해서 탐색을 해 주었다.

[ 소스코드 ]

#include<iostream>
#include<cstring>
#include<queue>
#include<vector>
 
#define endl "\n"
#define MAX 100000 + 1
using namespace std;
 
int N, M;
int Start, End, Answer;
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;
    cin >> Start >> End;
    for (int i = 0; i < M; i++)
    {
        int From, To, Cost;
        cin >> From >> To >> Cost;
        V[From].push_back(make_pair(To, Cost));
        V[To].push_back(make_pair(From, Cost));
    }
}
 
bool BFS(int Limit)
{
    queue<int> Q;
    memset(Visit, false, sizeof(Visit));
    Q.push(Start);
    Visit[Start] = true;
 
    while (Q.empty() == 0)
    {
        int Cur_Node = Q.front();
        Q.pop();
 
        if (Cur_Node == End) return true;
        for (int i = 0; i < V[Cur_Node].size(); i++)
        {
            int Next_Node = V[Cur_Node][i].first;
            int Next_Cost = V[Cur_Node][i].second;
 
            if (Visit[Next_Node] == false && Next_Cost >= Limit)
            {
                Visit[Next_Node] = true;
                Q.push(Next_Node);
            }            
        }
    }
    return false;
}
 
void Solution()
{
    int Low = 0;
    int High = 1000000;
    int Mid;
 
    while (Low <= High)
    {
        Mid = (Low + High) / 2;
        if (BFS(Mid) == true) Low = Mid + 1;
        else High = Mid - 1;
    }
 
    if (High == -1) cout << 0 << endl;
    else 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;
}