백준 16074번, Mountaineers 풀이

문제

백준 16074번

풀이

$ (x_{1}, y_{1}) $에서 $ (x_{2}, y_{2}) $로 가는 경로에서 방문하는 정점 중 최대 높이를 최소화하여야 합니다.

$ Q = 1 $이라고 가정하면,

 

높이가 $ mid $보다 작은 정점들만 사용하여 $ (x_{1}, y_{1}) $에서 $ (x_{2}, y_{2}) $로 가는 경로가 있는가

 

에 대한 결정 문제를 풀어야 합니다.

 

Union-Find 자료구조를 사용하여 $ mid $보다 작은 정점들을 순서대로 합쳐주는 것은 유사 크루스칼 알고리즘을 돌려 결정 문제를 해결할 수 있습니다.

 

높이 $ H $에 대한 이분 탐색 $ O(log H) $, 총 정점의 개수가 $ MN $이므로 유사 크루스칼 알고리즘을 돌리는데 $ O(MNlogMN) $이 걸립니다.

쿼리의 개수가 $ Q $개로 결정 문제를 $ Q $번 풀어야하므로, 시간복잡도는 $ O(QMNlogH \cdot logMN) $로 제한 시간 7초를 훨씬 넘어갈 것 같습니다.

 

 

각 쿼리에 대한 결정 문제를 해결할 때, 병렬 이분 탐색을 사용해서 $ mid $가 같은 쿼리끼리 모아 처리하면 $ log H $번의 스위핑으로 $ Q $개의 쿼리를 모두 처리할 수 있습니다.

 

한 번 스위핑할 때 $ O(MNlog MN + Qlog MN) $가 걸리고, 스위핑을 $ log H $번 하므로 전체 시간 복잡도는 $ O((MN+Q)logHlogMN) $가 됩니다.

소스코드

#include <bits/stdc++.h>

using namespace std;

int UF[501501];

int get_id(int x, int y) {
	return 1000 * x + y;
}

int find(int x) {
	return UF[x] = UF[x] == x ? x : find(UF[x]);
}

void merge(int x, int y) {
	x = find(x), y = find(y);

	if (x != y) {
		UF[x] = y;
	}
}

struct A {
	int x1, y1, x2, y2;
	int l, r;
};

int mp[501][501];
vector <A> query;
vector <vector<pair<int, int>>> grid;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int m, n, q, mx = 0;
	cin >> m >> n >> q;

	for (int x = 1; x <= m; x++)
		for (int y = 1; y <= n; y++)
			cin >> mp[x][y], mx = max(mx, mp[x][y]);

	grid.resize(mx + 1);
	for (int x = 1; x <= m; x++)
		for (int y = 1; y <= n; y++)
			grid[mp[x][y]].emplace_back(x, y);


	for (int i = 0; i < q; i++) {
		A a{};
		cin >> a.x1 >> a.y1 >> a.x2 >> a.y2;
		a.l = 1;
		a.r = mx + 1;

		query.push_back(a);
	}

	while (1) {
		int f = 0;
		vector <vector<int>> mid(mx + 1);
		for (int i = 0; i < q; i++)
			if (query[i].l != query[i].r) {
				f = 1;
				mid[(query[i].l + query[i].r) >> 1].push_back(i);
			}

		if (!f) break;

		for (int i = 1; i < 501501; i++) UF[i] = i;

		for (int i = 1; i <= mx; i++) {
			for (const auto &info : grid[i]) {
				int x = info.first, y = info.second;
				if (mp[x][y] == i) {
					if (x > 1 && mp[x - 1][y] <= i) merge(get_id(x, y), get_id(x - 1, y));
					if (y > 1 && mp[x][y - 1] <= i) merge(get_id(x, y), get_id(x, y - 1));

					if (x < m && mp[x + 1][y] <= i) merge(get_id(x, y), get_id(x + 1, y));
					if (y < n && mp[x][y + 1] <= i) merge(get_id(x, y), get_id(x, y + 1));
				}
			}

			for (const auto &k : mid[i]) {
				A &a = query[k];
				if (mp[a.x1][a.y1] <= i && find(get_id(a.x1, a.y1)) == find(get_id(a.x2, a.y2))) a.r = i;
				else a.l = i + 1;
			}
		}
	}

	for (const auto &_q : query) cout << (_q.l + _q.r >> 1) << "\n";
}

---

#감사합니다) justicehui.github.io/hard-algorithm/2020/02/24/pbs/