백준 1939 (중량제한) c++

문제

1939번: 중량제한

섬의 개수 n이 주어지고 섬과 섬사이에 무게를 최대로 옮길수 있는 간선의 정보 m개가 주어집니다.

섬과 섬사이에 최대로 옮길 수 있는 무게보다 큰 무게를 옮길 수 없습니다.

그리고 특정섬 a, b 가 주어지면 a와 b사이에 한번에 최대로 옮길 수 있는 무게를 구하면 됩니다.

 

예를 들어 0번 섬에서 9번섬으로 갈 수 있는 최대 무게는 11입니다.

따라서 11이상인 무게는 항상 옮길 수 있고 11미만인 무게는 항상 옮기지 못합니다.

이를 통해 이분탐색 parametric search를 이용할 수 있습니다.

bfs를 통한 그래프 탐색을 통해 mid값을 갱신해나가면서 해결 가능합니다.

 

하지만 이번에는 다른 방법을 활용해서 해결하겠습니다.

 예를 들어 무게가 13이면 파란색 트리, 초록색 트리에서만 이동이 가능합니다.

파란색 트리와 초록색 트리는 서로 독립관계 입니다.

여기서 3번과 5번 사이의 간선을 잇게 되면 11인 무게로 0번과 9번 노드를 건널 수 있는 최대무게 입니다.

이를 통해 Disjoint set 자료구조를 활용한 크루스칼 알고리즘을 생각 해볼 수 있습니다.

 

1) 먼저 간선이 큰 순서대로 정렬합니다.(내림차순으로 정렬)

2) 큰 간선대로 양 끝 섬을 잇습니다.

3) 2번을 반복하면서 a번 섬과 b번섬이 서로 같은 트리에 존재하면 break를 해주고 

그때 입력받은 간선의 가중치를 출력해주면 됩니다.

 

struct edge {
	int u, v;
	int c;
	bool operator<(edge rhs) {
		return c > rhs.c;
	}
};
vector<edge>Edge;

섬의 양끝과 그 사이를 잇는 간선의 가중치를 저장하기 위한 새로운 테이터 type인 edge를 따로 만들어 줍니다.

operator를 통해 내림차순으로 정렬을 하기위한 설정을 해줍니다.

cin >> n >> m;

for (int i = 0, u, v, c; i < m; i++) {
	cin >> u >> v >> c;
	Edge.push_back({ u, v, c });	
}
sort(Edge.begin(), Edge.end());

섬의 양 끝점을 입력받고 간선의 가중치 가지 입력받습니다.

내림차순으로 정렬해 줍니다.

 

int a, b;
cin >> a >> b;
for (int i = 1; i <= n; i++)
    parent[i] = i;
for (auto e : Edge) {
    if (check(e.u, e.v))
        Union(e.u, e.v);
    if (!check(a, b)) {
        cout << e.c;
        break;
    }
}
int Find(int u) {
    if (parent[u] == u)return u;
    return parent[u] = Find(parent[u]);
}
void Union(int u, int v) {
    u = Find(u);
    v = Find(v);
    parent[v] = u;
}
bool check(int u, int v) {
    u = Find(u);
    v = Find(v);
    if (u == v)return false;
    return true;
}

1, 2번째 줄에서 우리가 찾고자하는 섬 a, b를 입력받습니다.

3, 4 번째 줄에서 Union & Find를 하기위한 parent배열을 만들어 줍니다.

먼저 parent배열의 초기화는 각 섬의 번호와 같습니다.

ex) parent[1] = 1, parent[9] = 9

5~12 번째 줄까지 가장 값이 큰 간선의 가중치부터 섬을 이어줄것입니다.

22번째 줄 check 함수는 임의의 섬 u와 v가 같은 tree에 있는지 확인하는 함수입니다.

따라서 check(u, v) = true이면 u와 v는 서로소 관계이므로 Union 할 수 있습니다.

17번째 줄은 Union 함수입니다.

 

8번째 줄을 보면 우리가 찾고자 하는 섬 a, b가 check(a, b) = false 라면

a, b가 같은 tree에 있다는 의미이므로 그때 입력 받은 간선의 가중치를 출력해주면 됩니다.

 

시간복잡도 : O(|E|log|V|) 입니다.

---

전체 코드입니다.

#include<iostream>
#include<algorithm>
#include<cstring>
#include<vector>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<cmath>
#include<map>
#include<set>
#include<tuple>
using namespace std;
using ll = long long;
using ull = unsigned long long;
struct edge {
    int u, v;
    int c;
    bool operator<(edge rhs) {
        return c > rhs.c;
    }
};
vector<edge>Edge;
int n, m;
int parent[10001];
int Find(int u);
void Union(int u, int v);
bool check(int u, int v);
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    cin >> n >> m;
    for (int i = 0, u, v, c; i < m; i++) {
        cin >> u >> v >> c;
        Edge.push_back({ u, v, c });
        
    }
    sort(Edge.begin(), Edge.end());
 
    int a, b;
    cin >> a >> b;
    for (int i = 1; i <= n; i++)
        parent[i] = i;
    for (auto e : Edge) {
        if (check(e.u, e.v))
            Union(e.u, e.v);
        if (!check(a, b)) {
            cout << e.c;
            break;
        }
    }
    return 0;
}
int Find(int u) {
    if (parent[u] == u)return u;
    return parent[u] = Find(parent[u]);
}
void Union(int u, int v) {
    u = Find(u);
    v = Find(v);
    parent[v] = u;
}
bool check(int u, int v) {
    u = Find(u);
    v = Find(v);
    if (u == v)return false;
    return true;
}