[BOJ] 중량제한

[BOJ] 중량제한

Problem URL : 중량제한

풀이 1 (파라메트릭 서치)

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <cstring>

using namespace std;

vector<pair<int,int>> v[10001];
int n, m;
bool visit[10001];
int start, finish;

bool isPass(int weight) {
	memset(visit, false, sizeof(visit));
	visit[start] = true;
	queue<int> q;
	q.push(start);
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		if (cur == finish) return true;
		for (int i = 0; i < v[cur].size(); i++) {
			int next = v[cur][i].first;
			int nextW = v[cur][i].second;
			if (visit[next] || weight > nextW) continue;
			q.push(next);
			visit[next] = true;
		}
	}

	return false;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	cin >> n >> m;
	int maxW = 0;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		v[a].push_back({ b,c });
		v[b].push_back({ a,c });
		maxW = max(maxW, c);
	}
	cin >> start >> finish;

	int low = 0, high = maxW;
	int ans = 0;
	while (low <= high) {
		int mid = (low + high) / 2;
		if (isPass(mid)) {
		// 통과하면 중량을 높혀본다
			ans = mid;
			low = mid + 1;
		} else {
		// 통과실패하면 중량을 낮혀본다
			high = mid - 1;
		}
	}
	cout << ans << endl;

	return 0;
}

풀이 2 (크루스칼, Union-Find)

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

struct bridge {
    int start, finish, cost;
    bool operator < (const bridge& other) {
        return cost < other.cost;
    }
};

int n, m;
vector<bridge> bridges;

int group[10001];

int find(int p) {
    if (group[p] == p) return p;
    return group[p] = find(group[p]);
}

void merge(int p, int q) {
    p = find(p);
    q = find(q);
    group[p] = q;
}

int solution(int start, int finish) {
    for (int i = 1; i <= n; i++) group[i] = i;
    //내림차순 정렬
    sort(bridges.rbegin(), bridges.rend());
    /*중량제한이 큰 다리순으로 연결(merge)해보면서
     출발점과 도착점이 같은 group에 속하게 되는지 확인한다*/
    for (int i = 0; i < bridges.size(); ++i) {
        merge(bridges[i].start, bridges[i].finish);

        if (find(start) == find(finish)) {
            return bridges[i].cost;
        }
    }
    /*찾아낸 다리를 x라고 하자.
    x보다 큰 다리들만으로는 출발점과 도착점이 연결되지 않았다는 뜻이다 */
    return 0;
}

int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);    
    cin >> n >> m;
    while (m--) {
        int a, b, c;
        cin >> a >> b >> c;
        bridges.push_back({ a, b, c });
    }

    int start, finish;
    cin >> start >> finish;
    cout << solution(start, finish) << endl;
    
    return 0;
}

Comments

풀이 2가 풀이 1보다 2배 이상 빠르다! Union-Find를 이용한 알고리즘이 확실히 아이디어가 좋다.