BOJ 11085) 군사 이동

시간 제한 - 2s

메모리 제한 - 256MB

 

---

풀이

시작점과 끝점을 이을 수 있는 가장 넓은 길을 찾는 문제이다. 각 노드는 넓은 길을 우선으로 연결되며, 도중 시작점과 끝 점이 연결되었을 때 더 이상 좁은 길은 연결하지 않고 연산을 종료한다.

 

입력

정점의 수 p와 간선의 개수 w가 첫 줄에 입력되고, 시작점 c와 목적지 v가 다음 줄에 입력되며 양방향의 길에서 연결만 되면 되므로 순서는 상관없음.

이후 간선의 개수만큼 두 지점과 두 지점 사이의 넓이가 입력된다.

 

자료구조

두 점을 연결하는 도로의 넓이와 두 도로의 위치를 담기 위한 <int width, <int start, int end>>형 배열

 

로직

1. 입력받은 정점의 수 만큼 배열을 초기화 시켜준 후 입력을 받는다.

2. 벡터 컨테이너의 back()을 통해 후방부터 넓은 도로 순서로 접근하기 위해 넓이를 기준으로 오름차순 정렬 

3. 컨테이너가 비거나 시작점과 끝 점이 연결 될 때까지 union 연산을 통해 두 정점을 연결해줌

정렬이 완료된 컨테이너에 back() 연산 시 접근하는 자료는 항상 가장 넓은 도로이며, 시작점과 도착점 사이에 존재하지 않더라도 이후 사용되는 연결의 넓이는 항상 해당 넓이보다 좁거나 같기 때문에 결과에 영향을 주지 않는다는 것을 증명, 넓은 순서대로 연결하다가 시작점과 끝 점이 연결된다면 반복을 종료함

4. 반복이 종료되었을 때 마지막으로 연결한 도로의 넓이를 출력

---

코드

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

using namespace std;
using conn = pair<int, pair<int, int>>;
vector<int> parent;
vector<conn> conns;

int find(int node) {
	if (node == parent[node]) return node;
	return parent[node] = find(parent[node]);
}

void merge(int lhs, int rhs) {
	lhs = find(lhs);
	rhs = find(rhs);

	if (lhs > rhs) parent[lhs] = rhs;
	else parent[rhs] = lhs;
}

int main() {
	int n, w, c, v;
	
	cin >> n >> w >> c >> v;
	parent.resize(n);
	conns.resize(w);
	
	for (conn& i : conns) cin >> i.second.first >> i.second.second >> i.first;
	for (int i = 0; i < n; i++) parent[i] = i;

	sort(conns.begin(), conns.end());
	int ret;
	while (find(c) != find(v)) {
		ret = conns.back().first;
		merge(conns.back().second.first, conns.back().second.second);
		conns.pop_back();
	}
	cout << ret << endl;
	return 0;
}

 

컨테이너를 넓이 순으로 정렬할 때, M * log M 만큼의 시간이 걸리므로 전체적인 시간 복잡도도 이와 동일.