백준 1939 (C++) 중량제한 (메모리 초과 -> 4496KB, 시간-32ms)

분리 집합

분리 집합을 이용해 풀었다.

분리 집합의 기본을 연습하고 싶다면 이 문제를 풀어보자

2021.09.28 - [PS/백준] - 백준 1717 (C++) 집합의 표현

백준 1717 (C++) 집합의 표현

 

시간 비교(BFS vs Union set)

 

찾아보니 이분탐색 + bfs를 이용한 방법이 많다.

맨 위가 나의 제출인데 굉장히 적은 시간과 메모리가 걸린 것으로 보인다.

 

 

 

처음엔 주어진 집합을 전부 union하고

각각의 비용을 2차원 인접 행렬에 저장한 뒤

입력의 from과 to(공장이 위치한 섬의 노드 번호)의 행렬값 cost를 출력하려했는데 메모리 초과가 났다.

 

 

2차원 배열을 안쓰는 방법이 없을까? 하다가 

 

from과 to(두 공장이 위치한 섬의 노드 번호)가 연결된 순간의 cost를 출력해주면 될 것 같다는 생각이 들었다.

결과는 AC!

 

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long;
const int MAX = 10001;
const int INF = 987654321;
int n, m,ans = 0;
int Parent[MAX]; // Parent[node] == parent of node
//int W[MAX][MAX];
struct Edge {
    int s,e,cost;
    bool operator<(const Edge &e) const {
        return cost > e.cost;
    }
};
vector<Edge> v;
int getParent(int n1) {
    if (Parent[n1] == n1) return n1;
    else return Parent[n1] = getParent(Parent[n1]);
}
void unionParent(int n1, int n2) {
    n1 = getParent(n1);
    n2 = getParent(n2);
    if (n1 != n2) {
        Parent[n2] = n1;
    }
}
int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 0; i <= n; i++) {
        Parent[i] = i;
    }
    for (int i = 0; i < m; i++) {
        int a,b,c;
        cin >> a >> b >> c;
        v.push_back(Edge{a,b,c});
    }
    sort(v.begin(), v.end());
    
    int from, to;
    cin >> from >> to;
    for (auto cur : v) {
        unionParent(cur.s, cur.e);
        if (getParent(from) == getParent(to)) {
            cout << cur.cost;
            break;
        }
        //W[cur.e][cur.s] = W[cur.s][cur.e] = max(W[cur.s][cur.e], cur.cost);
    }
    //cout << W[from][to];
    return 0;
}