백준 1939번 중량제한

문제 링크입니다: https://www.acmicpc.net/problem/1939

BFS(Breadth First Search) 알고리즘과 이진 탐색(Binary Search)를 같이 사용해야 풀 수 있는 문제였습니다.

문제가 조금 난해한데 결국 시작섬에서 도착섬까지 운반할 수 있는 최대 중량을 구하는 문제였습니다.

알고리즘은 아래와 같습니다.

1. 공장1과 공장2 그리고 중량 제한을 양방향으로 입력받습니다. 이 때, 이진 탐색을 위해 최대 중량 제한을 업데이트합니다.

2. 여태까지 입력 받은 중량 제한 중 하나가 답이므로 low = 0, high = 최대 중량 으로 초기화하여 이진탐색을 합니다. 중량제한이 mid일 때 BFS 함수를 호출해서 시작섬에서 도착섬까지 운반 가능하면 low를 업데이트하고 운반할 수 없다면 high를 업데이트합니다.

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

#include <iostream>

#include <vector>

#include <queue>

#include <algorithm>

#include <cstring> //memset

using namespace std;

 

const int MAX = 100000 + 1;

 

int N, M;

int start, finish;

vector<pair<int, int>> graph[MAX];

bool visited[MAX];

 

//전형적인 BFS

bool BFS(int cost)

{

        queue<int> q;

        q.push(start);

        visited[start] = true;

 

        while (!q.empty())

        {

                 int curFactory = q.front();

                 q.pop();

 

                 if (curFactory == finish)

                         return true;

 

                 for (int i = 0; i < graph[curFactory].size(); i++)

                 {

                         int next = graph[curFactory][i].first;

                         int nextCost = graph[curFactory][i].second;

 

                         //중량 제한이 cost일 때 다리를 건널 수 있는지 여부를 판별하기 위해

                         if (!visited[next] && cost <= nextCost)

                         {

                                 visited[next] = true;

                                 q.push(next);

                         }

                 }

        }

        return false;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //cin 실행속도 향상

        cin >> N >> M;

 

        int maxCost = 0;

 

        for (int i = 0; i < M; i++)

        {

                 int factory1, factory2, cost;

                 cin >> factory1 >> factory2 >> cost;

                 //양방향 그래프

                 graph[factory1].push_back(make_pair(factory2, cost));

                 graph[factory2].push_back(make_pair(factory1, cost));

                 maxCost = max(maxCost, cost); //최대 중량 업데이트

        }

 

        cin >> start >> finish;

        //이진 탐색

        int low = 0, high = maxCost;

        while (low <= high)

        {

                 memset(visited, false, sizeof(visited));

 

                 int mid = (low + high) / 2;

                 if (BFS(mid))

                         low = mid + 1;

                 else

                         high = mid - 1;

        }

        cout << high << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~