[ boj : 1939]중량제한

[문제] : https://www.acmicpc.net/problem/1939

1939번: 중량제한

[조건] : N개의 섬과 M개의 다리가 주어지며 각 다리에는 물품의 무게를 최대로 버틸수 있는 중량제한 W가 주어집니다.A섬 부터 B섬까지 운송할 수 있는 물품의 최대 무게를 구하면 됩니다.여러다리를 거쳐서 갈 수도 있습니다.

 

[구현방법] : 

첫번째로 BFS,DFS + 이분탐색(파라메트릭)으로 푸는 방법이 존재합니다.

두번째로 MST를 떠올려 반대로 생각한 후 접근 하는 방법이 존재합니다.

나머지는 전 잘 모르겠군요 ㅎㅎ (찾아보시면 DFS+메모이제이션 방법을 통해서도 풀더라구요)

 

일단 첫번째 방법은

물품의 무게(ans)가 주어졌을때 다리를 건널 수 있는 상황은 다리가 가지고 있는 중량제한(w)가 물품의 무게(ans)보다 크거나 같으면 됩니다. A섬에서 B섬까지 다리들의 중량제한(w)가 주어진 물품의 무게(ans)보다 작아 더이상 건널수 있는 다리가 존재하지 않게 된다면 현재 정해진 물품의 무게를 줄이면 되겠죠, 반대로 다리를 전부 통과해 B섬까지 도달했다면 물품의 무게를 올려서 다시 탐색해 최대물품의 무게를 구하면 됩니다.즉, 이분탐색(파라메트릭)을 이용하여 물품의 무게(ans)를 구할 수가 있습니다.

A섬에서 B섬까지 경로가 있는지는 BFS와 DFS를 이용하여 확인을 하면 되겠죠.(이때 주의할 점은 각 섬들과 다리들의 정보를 저장하기 위해 인접행렬을 사용하면 안된다는 것 입니다. N은 최대 10만이니 당연히 메모리 초과가 발생하게 됩니다. "이렇게 정점의 수가 많고 간선의 수가 V^2에 한참 못 미치는 문제에서는 인접 행렬이 아니라 인접 리스트를 통해 해결하는 것이 바람직합니다."-djm03178님의 조언입니다)

 

[소스] : 

#include<iostream>
#include<vector>
#include<cstring>
#define SIZE 100001
 
using namespace std;
 
int a, b, w;
vector<pair<int, int>> v[SIZE];
bool visit[SIZE];
 
bool DFS(int x, int weight);
 
int main()
{
    int n, m,ans=0;
    
    cin >> n >> m;
 
    for (int i = 0; i < m; i++) {
        cin >> a >> b >> w;
        v[a].push_back({ b,w });
        v[b].push_back({ a,w });
    }
 
    cin >> a >> b;
 
    int left = 0, right = 1000000000;
 
    while (left <= right)
    {
        int mid = (left + right) / 2;
        if (DFS(a, mid)) {
            ans = mid;
            left = mid + 1;
        }
        else
            right = mid - 1;
        memset(visit, false, sizeof(visit));
    }
    cout << ans;
    return 0;
}
bool DFS(int x,int weight)
{
    visit[x] = true;
    if (x == b)
        return true;
    for (auto u : v[x])
    {
        if (!visit[u.first] && weight <= u.second) {
            if (!DFS(u.first, weight))continue;
            else
                return true;
        }
    }
    return false;
}

 

두번째 방법은 

최소신장트리(MST)의 개념을 이용해 해결하는 방법입니다.(이 개념을 모른다면 먼저 습득하고 오시는걸 추천드립니다.)

mst는 모든 정점들을 연결하는 간선들의 가중치의 합이 최소가 되는 그래프를 뜻합니다.

이 개념을 조금만 변형해 이 문제에 적용이 가능합니다.

우린 A섬에서 B섬까지 운반할 수 있는 물품의 최대값을 구해야 하니 mst와 반대로 내림차순으로 간선들을 정렬을 한 후 A섬에서 B섬까지 연결이 되는 순간의 선택된 다리의 제한무게를 출력해 내면 됩니다.

왜 A섬에서 B섬이 연결되는 순간의 선택된 다리의 제한무게인가요??

우린 이미 다리들의 가중치를 내림차순으로 정렬을 해놓은 상태입니다.그리고 다리의 가중치가 큰 순서대로 선택에 섬들을 연결해 나아갑니다. 따라서 A섬에서 B섬까지 연결된 순간 다리의 가중치가 물품의 무게의 최대값이 되는것이죠.물품은 A섬에서 B섬까지 다리의 가중치보다 작거나 같으니까요. 

mst알고리즘 중에 대표적인 크루스칼 알고리즘을 이용해서 해결하면 됩니다.

 

[소스] : 

 

 

#include<iostream>
#include<vector>
#include<queue>
#include<algorithm>
 
using namespace std;
 
struct edge {
    int node[2];
    int distance;
    edge(int a, int b, int distance)
    {
        this->node[0] = a;
        this->node[1] = b;
        this->distance = distance;
    }
    bool operator < (const edge &e) {
        return distance > e.distance;
    }
};
 
vector<edge> v;
int parent[10001];
void union_parent(int a, int b);
int find_parent(int x);
int check_parent(int a, int b);
 
int main()
{
    int n, m;
    int a, b,w,ans=0;
    cin >> n >> m;    
    
    for (int i = 0; i < m; i++) {
        cin >> a >> b>>w;
        v.push_back({ a,b,w });
    }
    sort(v.begin(),v.end());
 
    cin >> a >> b;
    for (int i = 1; i <= n; i++)
        parent[i] = i;
    for (int i = 0; i < v.size(); i++)
    {
        if (check_parent(v[i].node[0], v[i].node[1]))
            union_parent(v[i].node[0], v[i].node[1]);
        if (!check_parent(a, b)) {
            cout << v[i].distance;
            break;
        }
    }
    return 0;
}
void union_parent(int a, int b)
{
    a = find_parent(a);
    b = find_parent(b);
 
    parent[b] = a;
}
int find_parent(int x)
{
    if (parent[x] == x)
        return x;
    return parent[x] = find_parent(parent[x]);
}
int check_parent(int a, int b)
{
    a = find_parent(a);
    b = find_parent(b);
 
    if (a == b)
        return 0;
    else
        return 1;
}

#어색한 표현이나 설명이 틀린부분 그리고 필요 없는 코드가 존재한다면 언제라도 태클 걸어주시면 감사하겠습니다