백준 1939번 중량 제한

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

1939번: 중량제한

문제

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인 다리가 존재한다는 의미이다. 서로 같은 두 도시 사이에 여러 개의 다리가 있을 수도 있으며, 모든 다리는 양방향이다. 마지막 줄에는 공장이 위치해 있는 섬의 번호를 나타내는 서로 다른 두 정수가 주어진다. 공장이 있는 두 섬을 연결하는 경로는 항상 존재하는 데이터만 입력으로 주어진다.

 

출력

첫째 줄에 답을 출력한다.

 

풀이

이분 탐색 + dfs/bfs 문제이다.

풀이는 이분 탐색 + dfs 입니다!

처음에 2차원 배열로 v[a][b] = a~b 다리의 중량 제한으로 두고,

boolean 배열을 만들고 하다 보니 메모리 초과가 나버려서 다시 푼 문제이다.

그래서 vector에 pair로 <연결된 섬, 중량 제한>으로 풀고 dfs를 돌리니 풀 수 있었다.

 

문제 설명부터 하자면, 섬과 섬 사이에 각각의 다리가 있고 공장이 있는 곳은 두 섬뿐이다.

문제에서 요구하는 바는 이동해서 옮길 수 있는 중량의 최댓값이고, 중량 범위가 10억까지이기 때문에 이분 탐색을 이용해서 문제를 풀면 된다.

하지만, 우선 x만큼의 중량으로 처음 공장 섬(first)에서 다음 공장 섬(second)으로 갈 수 있는가? 를 판단해야 하기 때문에 이 문제는 이분 탐색에 dfs/bfs 알고리즘을 더해주어야 하는 문제이다.

우선, 이분 탐색을 위해 범위를 설정하자면,

 

• left(최솟값) : 1
• right(최댓값) : 10억
• mid(중간값) : (left + right) / 2

로 두고, mid의 범위를 좁혀나간다.

mid를 정했으면 dfs에 mid를 넘기고, 이 mid값으로 dfs를 이용해 first 섬에서 second 섬까지 갈 수 있는 가?를 구한다.

 

소스 코드

#define MAX 1000000000;
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
 
int n, m;
int first, second;
bool check1[100001];
vector<pair<int, int> >v[100001];
 
 
 
bool dfs(int st, int t) { //st : first , t : mid
    if (check1[st]) return false; //이미 방문했다면
    check1[st] = true;
    if (st == second) return true; //도착 시
    for (auto& p : v[st]) {
        int next = p.first; //다음 섬
        int cost = p.second;
        if (cost >= t) {
            if (dfs(next, t)) return true;
        }
        
    }
    return false;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i < m; i++) { //다리 입력받기
        int a, b, c; scanf("%d%d%d", &a, &b, &c);
        v[a].push_back(make_pair(b, c));
        v[b].push_back(make_pair(a, c));
    }
    scanf("%d%d", &first, &second);
    int left = 1;
    int right = MAX;
    int ans = 0;
    while (left <= right) {
        int mid = left + (right - left) / 2;
        memset(check1, false, sizeof(check1));
        if (dfs(first, mid)) { //옮길 수 있을 경우
            ans = mid;
            left = mid + 1; //중량 증가
        }
        else right = mid - 1; //중량 감소
    }
    printf("%d", ans);
    return 0;
}

개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~