취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 31115번 문제인 Graph Theory이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/31115

어떤 에지를 지워서 구하고자 하는 최솟값이 $K$ 이하가 되게 할 수 있다면 $K$보다 더 큰 수 $K^{\prime }$ 이하가 되게도 항상 할 수 있고, $K$ 이하가 되게 할 수 없다면 $K$보다 더 작은 수 $K^{″}$ 이하가 되게 할 수 도 없음을 관찰하자. 따라서 최솟값이 $K$ 이하가 되게 할 수 있는 K를 이분탐색을 통해 구하는 것을 시도할 수 있다. 그리고 이것이 답이 됨은 어렵지 않게 확인할 수 있다.

어떤 값 $K$에 대하여 구하고자 하는 값이 $K$ 이하인지 확인하는 알고리즘을 구성해보자. 각 두 노드의 쌍 사이에는 두 점을 잇는 두 단순경로가 존재한다. 각 단순경로에 대하여 해당 경로를 구성하는 에지를 하나 지울 시 두 점을 잇는 최단거리는 다른 단순경로의 거리와 같게 되는데, 이 값이 $K$보다 크다면 지운 에지를 포함하는 경로에서 에지를 지우면 원하는 결과를 얻을 수 없게 된다. 따라서 이를 통해 두 노드의 쌍에 대하여 지우면 안되는 에지가 무엇인지를 찾을 수 있다.

각 노드의 쌍에 대하여 지울 에지들이 무엇인지 전부 구하고, "지우면 안되는 에지"가 아닌 에지가 존재하는지를 판단하자. 이 과정은 $O(N+M)$에 가능하다. imos법을 활용하자.

$O(N+M)$ 과정을 $\lg N$회 반복해 이분탐색을 마치므로, 테스트케이스 하나를 해결하는 데에 드는 시간복잡도는 $O((N+M)\lg N)$이 된다.

아래는 제출한 소스코드이다.

#include <iostream>
#include <utility>
using namespace std;

int N, M, X[200000], Y[200000];
int A[200002];
bool func(int K) {
	for (int i = 1; i <= N; i++) A[i] = 0;
	for (int k = 0; k < M; k++) {
		int val = Y[k] - X[k];
		if (val > K) A[1]++, A[X[k]]--, A[Y[k]]++;
		if (N - val > K) A[X[k]]++, A[Y[k]]--;
	}
	for (int i = 1; i <= N; i++) {
		A[i] += A[i - 1];
		if (!A[i]) return 1;
	}
	return 0;
}

int L, R;
void solve() {
	L = 0, R = N;
	for (int i = 0; i < M; i++) {
		int x, y; cin >> x >> y;
		if (x > y) swap(x, y);
		if (x == y) {
			i--, M--;
			continue;
		}
		X[i] = x, Y[i] = y;
	}
	while (L < R) {
		int mid = (L + R) / 2;
		if (func(mid)) R = mid;
		else L = mid + 1;
	}
	cout << L << '\n';
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	while (cin >> N >> M) solve();
}