백준 11085: 군사 이동

문제 요약

전쟁 당시 Baekjoon World의 국왕은 Cube World를 공격할 작전을 세운 적이 있습니다. Baekjoon World와 Cube World는 p개의 지점과 w개의 길로 표현됩니다. 모든 길은 양방향이며, 각 길마다 너비가 존재하여 이에 비례하는 수의 군사가 지나갈 수 있습니다.

Baekjoon World의 국왕은 군사들이 뭉치는 것이 유리하다고 생각해서, 미리 Cube World로 가는 경로를 정해 두고 그 경로로만 모든 군사를 보냈습니다. Baekjoon World의 국왕은 총명해서, 경로 상에 있는 길 중 너비가 가장 좁은 길의 너비를 최대화하는 경로를 택했습니다.

그런데 전쟁 때문에 어느 길로 보냈는지에 대한 기록이 불타 없어져 버렸습니다. 전쟁사를 완성하려면 이 기록이 꼭 필요합니다. 위대한 과학자인 당신이 다시 복구해 주세요.

문제 분류

• 자료 구조
• 그래프 이론
• 그래프 탐색
• 분리 집합

문제 풀이

노드의 수와 간선의 개수가 주어지고, 서로 다른 두 노드를 잇는 경로의 가중치를 그 경로를 구성하는 간선의 최소 가중치로 잡는다고 했을 때, 어떠한 두 노드 사이의 경로 중 최대의 가중치를 구하는 문제이다.

주어진 간선을 가중치를 기준으로 내림차순 정렬을 한 뒤, 큰 간선부터 삽입해주었다. 해당 간선의 두 노드를 하나의 집합으로 처리하고, 현재 간선이 정답 후보가 되겠다. 만약 현 간선으로 인해 c와 v가 하나의 집합으로 묶여있다면 경로가 이어진 것으로 판단하여 현재 가중치를 출력하면 된다.

가중치를 정렬하여 사용한다는 점에서 그리디와도 비슷하다고 느꼈다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <map>

using namespace std;

int p[1000];

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

void merge(int a, int b) {
	a = find(a);
	b = find(b);
	if (a == b) return;
	p[b] = a;
}

int main()
{
	int n, w, c, v, in, in2, in3, res;
	multimap<int, pair<int, int>,greater<>> m;
	scanf("%d%d", &n, &w);
	scanf("%d%d", &c, &v);
	for (int i = 0; i < w; i++) {
		scanf("%d%d%d", &in, &in2, &in3);
		m.insert({ in3, {in,in2} });
	}
	for (int i = 0; i < n; i++)
		p[i] = i;
	auto iter = m.begin();
	while (find(c) != find(v)) {
		res = iter->first;
		merge(iter->second.first, iter->second.second);
		iter++;
	}
	cout << res;
}