BOJ 30906 Isolated Island

문제 링크입니다.

문제 요약

주어진 평면 그래프의 외부를 제외한 면 중, 외부까지의 거리¹가 같으면서 간선을 공유하는 면이 존재하는 지 판정하세요.

풀이

인접한 두 면 사이의 거리 차이가 1 이하임을 알 수 있습니다. 만약 두 인접한 면의 거리 홀짝성이 같다면 두 면의 거리가 서로 같아 문제의 조건을 만족하게 됩니다.

따라서 문제에서 요구하는 조건을 만족하지 않을 필요충분조건은 모든 인접한 면의 거리 홀짝성이 서로 다를 것이고, 이는 주어진 평면 그래프의 듀얼이 이분 그래프임을 의미합니다.

이분 그래프임과 홀수 사이클이 존재하지 않음은 서로 동치입니다. 따라서 모든 사이클이 짝수 사이클인 지 판정하면 됩니다. 적당한 단위 사이클을 잡았을 때 이 사이클들이 모두 짝수 사이클이라면 홀수 사이클이 만들어질 수 없음을 알 수 있습니다. 이 문제 상황의 경우 이 단위 사이클은 원본 평면 그래프의 각 꼭짓점에서 만나는 면들을 의미합니다.

그래서 모든 꼭짓점마다 짝수 개의 간선이 모이는 지 확인하면 문제를 해결할 수 있습니다. 문제는 간선이 선분으로 주어져서 꼭짓점 수가 매우 많아질 수 있다는 건데, 사실 어차피 선분의 중간에서 만나는 경우는 간선이 둘로 갈라지므로 홀짝성을 따지는 데에는 아무 영향을 안 미칩니다.

따라서 단순히 주어지는 선분들의 양 끝 점만을 모아 모두 짝수 번 출현하는 지 확인하는 것으로 문제를 해결할 수 있습니다!

코드

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
map<pii, int> mp;
int main(){
	cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);
	int n; cin >> n; for(int i = 1; i <= n; i++){
		int a, b, c, d; cin >> a >> b >> c >> d;
		mp[{a,b}]++; mp[{c,d}]++;
	}
	for(auto& [key, val] : mp) if(val&1) return !(cout << "yes");
	cout << "no";
}

---

1. 이 문제에서 거리는 어떤 면에서 외부에 도달하기 위해 지나야 하는 모서리 수의 최솟값입니다. 꼭짓점을 통해 지나갈 수는 없습니다. ↩︎