알고리즘 문제 풀이7
알고리즘 문제 풀이 7
최근에 푼 재미있는 문제들을 포스팅 해보겠습니다.
[BOJ 9208 링월드]
이 문제는 원형으로 나열되어 있는 $M$개의 도시가 있고, 연속된 도시들로 이루어진 $N$개의 구간이 있을 때, $N$개의 구간에서 겹치지 않게 도시를 하나씩 고를 수 있는가를 답해야 하는 문제입니다.
우선, M개의 도시가 원형이 아니라 선형으로 나열되어 있다면 어떨까요? 이 문제는 매우 간단한 그리디로 풀 수 있습니다. 왼쪽 도시에서부터 쭉 보면서 현재 도시를 고를 수 있는 구간들 중 오른쪽 끝 도시가 가장 왼쪽에 있는 구간에게 현재 도시를 할당하는 것이 최적입니다. 따라서 이 알고리즘으로 모든 구간에게 도시를 할당할 수 있으면 답은 YES, 그렇지 않으면 NO 라는 것을 쉽게 알 수 있습니다.
이 알고리즘은 $O(NlogN)$ 에 동작하도록 작성할 수 있습니다.
그렇다면, 도시가 원형으로 나열된 문제는 어떻게 풀 수 있을까요?
이 문제가 bipartite matching 에서 perfect matching 이 존재하는지를 묻는 문제라는 점에서 홀의 결혼 정리의 관점에서 이 문제를 관찰해 볼 수 있습니다.
홀의 결혼 정리에 의해 perfect matching 이 존재하는 것과 구간들의 집합의 임의의 부분집합 $A$를 생각했을 때, $A$의 크기보다 $A$에 포함된 구간들의 합집합의 크기가 더 크거나 같다는 것이 필요 충분 조건임을 알 수 있습니다.
이 때, 원형 버전의 문제에 대응되는 아래와 같은 선형 버전의 문제를 생각해 봅시다.
$2M$개의 도시가있고, 원형 버전의 문제에서 주어진 구간 [$l_i, r_i$]에 대해 $l_i \leq r_i$이면 구간 [$l_i, r_i$], [$l_i + M, r_i + M$]을 추가하고, $l_i > r_i$이면 구간 [$l_i, r_i + M$]을 추가한다.
우선, 선형 버전에서 홀의 결혼 정리의 조건이 성립한다면, 원형 버전에서 홀의 결혼 정리의 조건이 성립함은 자명합니다.
그렇다면 원형 버전에서 홀의 결혼 정리의 조건이 성립하면 선형 버전에서도 홀의 결혼 정리의 조건이 성립할까요?
$N \leq M$ 이라면 이 조건도 성립한다는 것을 어렵지 않게 증명할 수 있습니다.
우선 부정을 가정합시다. 즉, 원형 버전에서 홀의 결혼 정리의 조건이 성립할 때, 선형 버전에서 홀의 결혼 정리의 조건이 성립하지 않는 구간들의 어떤 부분 집합 $A$가 존재한다는 것을 가정하는 것입니다. 우선, 집합 $A$를 원소인 구간들의 합집합이 연속된 도시들로 구성된 경우라고 생각하여도 문제가 없습니다. 왜냐하면, 구간들의 합집합이 불연속인 도시들로 구성된 경우 연속된 도시들과 대응되는 부분 집합으로 쪼갤 수 있고, 이 중 적어도 하나는 홀의 결혼 정리의 조건을 만족하지 않을 것이기 때문입니다.
따라서 $A$의 원소들의 합집합은 선형 버전의 도시 배열에서 연속인 도시의 구간을 나타냅니다.
한편, 이 도시 구간의 길이가 $M$보다 작다면 원형 버전의 문제로 정확히 대응 시킬수 있으므로 홀의 결혼 정리의 조건을 당연히 만족시킬 것입니다. 따라서 이 도시 구간의 길이는 $M$보다 큽니다.
도시 구간의 길이가 $M$보다 크면서 홀의 결혼 정리의 조건을 만족하지 않으려면 당연히 구간은 $N$개보다 많이 선택되었을 것입니다. 그러면 $A$ 당연히 원형 버전에서 같은 구간에서 파생된 한 쌍의 구간들중 적어도 한 쌍을 모두 포함하고 있을 것입니다. 우리는 그러한 쌍 중 가장 왼쪽에 있는 한 쌍을 골라서 중 오른쪽에 있는 구간을 남기고 왼쪽에 있는 구간을 모두 제외한 집합을 생각해 봅시다.
이 집합은 원래 생각한 $A$에 비해 원소의 합집합에 대응되는 도시의 개수는 $M$개 이상이 줄어들며 구간의 개수(집합의 크기)는 $N$개 이하가 줄어들기 때문에 $N \leq M$에서 남은 구간들의 집합 또한 홀의 결혼 정리의 조건을 만족시키지 않아야 하는데, 이는 원형 버전의 문제에 대응 시킬수 있는 집합이므로 모순입니다.
따라서 증명을 완료하였습니다.
따라서 $N \leq M$이라면 원형 버전의 문제에서 perfect matching 이 존재한다는 것과 그에 대응되는 선형 버전의 문제에서 perfect matching이 존재한다는 것이 동치입니다.
따라서 위에서 제시한 선형 버전을 해결하는 알고리즘을 통해 원형 버전의 문제도 $O(NlogN)$ 시간에 해결할 수 있습니다.
#include<bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
int M, N;
vector<pii> seg;
priority_queue<int> pq;
int Xn;
vector<int> X;
void main2() {
scanf("%d %d", &M, &N);
seg.clear();
X.clear();
for(int i = 0; i < N; i++) {
int l, r; scanf("%d %d", &l, &r);
if(l <= r) {
seg.push_back(pii(l, r));
seg.push_back(pii(l + M, r + M));
X.push_back(l);
X.push_back(l + M);
}
else {
seg.push_back(pii(l, r + M));
X.push_back(l);
}
}
X.push_back(2 * M);
sort(seg.begin(), seg.end());
sort(X.begin(), X.end());
X.resize(unique(X.begin(), X.end()) - X.begin());
Xn = X.size();
if(M < N) {
printf("NO\n");
return;
}
while(!pq.empty()) pq.pop();
int pos = 0;
for(int i = 0; i < Xn - 1; i++) {
while(pos < seg.size() && seg[pos].first == X[i]) {
pq.push(-seg[pos].second);
pos++;
}
int x = X[i];
while(x < X[i + 1] && !pq.empty()) {
int t = -pq.top(); pq.pop();
if(t < x) {
printf("NO\n");
return;
}
x++;
}
}
if(pq.empty()) printf("YES\n");
else printf("NO\n");
}
int TC;
int main() {
scanf("%d", &TC);
while(TC--) main2();
}
[BOJ 15879 Edge Coloring]
이 문제는 다중 간선이 존재할 수 있는 그래프가 주어지면, 아래의 조건을 만족하도록 몇개의 간선을 골라서 색칠하는 경우의 수를 구하는 문제입니다.
주어진 그래프의 모든 정점에 대해 색칠된 간선의 수가 홀수개여야 한다.
만일, 주어진 그래프가 여러개의 컴포넌트로 구성된다면, 각 컴포넌트에 대해 답을 구한뒤 곱해주기만 하면, 원하는 답을 얻을 수 있을 것이기 때문에 우리는 연결된 그래프에 대해서 문제를 풀어주기만 하면 됩니다.
그렇다면 연결된 그래프가 주어지면 우리는 언제나 조건을 만족한는 색칠을 얻을 수 있을까요?
그렇지 않습니다. 대표적으로 떠올릴 수 있는 경우가 정점이 홀수개가 있는 경우입니다. 이 경우에는 간선이 어떤식으로 주어지더라도 색칠이 불가능합니다. 왜일까요?
조건을 만족하는 색칠이 있다고 가정합시다.
여기서 우리는 서로 연관되어 있는 (정점, 간선) 쌍의 개수를 두가지 관점에서 세어 볼 것입니다.
첫번째 관점은 정점의 관점입니다. 각 정점마다 색칠된 간선의 수를 모두 세어줍니다. 조건에 의해 이들의 합은 홀수일 것입니다.
두번째 관점은 간선의 관점입니다. 각 간선마다 연관된 정점의 수를 모두 세어줍니다. 간선마다 연관된 정점은 2개씩 있으므로 이들의 합은 짝수일 것입니다.
같은 대상의 개수의 기우성이 다르므로 이러한 대상의 존재가 모순임을 알 수 있습니다. 따라서 조건을 만족하는 색칠이 없다는 것을 알 수 있습니다.
그렇다면 그 외의 경우 즉, 정점이 짝수개인 경우에는 언제나 조건을 만족하는 색칠이 존재 할까요?
존재성 자체는 간단하게 보일 수 있습니다.
정점이 짝수개면서 연결된 그래프이므로 임의로 정점을 2개씩 짝지어도 짝지어진 두 정점을 잇는 경로가 존재합니다.
모든 쌍에 대해 두 점을 잇는 경로중 하나를 마음대로 골라서 이어봅니다.
그러면 그래프에서 각 간선이 경로의 일부로서 사용된 횟수가 있을텐데, 이 중 홀수번 사용된 간선만 색칠해주면 조건을 만족하는 색칠입니다.
이는 경로를 잇는 과정을 간선의 색칠여부를 반전시키는 행위라고 해석하면 비교적 직관적으로 알 수 있습니다.(모든 경로를 symmetric difference 한 결과)
그렇다면 이제 모든 색칠의 경우의 수는 어떻게 구하는 것인지 알아봅시다.
비교적 쉬운 문제를 풀어봅시다. 같은 문제이지만 조건이 아래와 같이 바뀐 문제를 생각해 봅시다.
주어진 그래프의 모든 정점에 대해 색칠된 간선의 수가 짝수개여야 한다.
다음과 같은 관찰을 해봅시다.
이 그래프 위의 사이클을 몇 개만 생각해 봅시다. 그리고 이들을 symmetric difference 한 결과를 색칠해 봅시다.
이 색칠은 조건을 만족하는 색칠인가요? 그렇습니다. 왜냐하면 symmetric difference 한 결과는 간선이 상호 배타적인 단순 사이클들의 집합일 것이기 때문에 각 정점은 그 정점을 지나는 사이클의 들어오는 간선과 나가는 간선을 모두 가질 것이기 때문입니다.
이 관찰로부터 다음과 같은 가정을 해볼 수 있습니다.
사이클들을 symmetric difference한 결과로 나올수 있는 모든 모양의 개수와 조건을 만족하는 색칠의 개수가 같을 것이다.
우선 사이클들을 symmetric difference한 결과는 그에 대한 색칠에 대응됩니다. 또한 조건을 만족하는 색칠은 어떤 사이클들의 symmetric difference로 해석할 수 있음을 수학적 귀납법을 통해 어렵지 않게 알 수 있습니다.
그렇다면 이 비교적 쉬운문제는 결국 사이클들을 symmetric difference한 결과로 나올수 있는 모든 모양의 개수를 묻는 문제과 같습니다.
| 아래의 링크의 글을 읽어보면 모든 모양이 cycle basis의 부분집합에 대응된다는 사실을 알 수 있고 따라서 색칠의 개수는 $2^{ | cycle basis | }$ 라는 것을 알 수 있습니다. |
링크: https://en.wikipedia.org/wiki/Cycle_basis
이제 본 문제로 돌아와 봅시다. 조금만 생각해보면 본 문제의 색칠과 쉬운 문제의 색칠이 일대일 대응된다는 사실을 알 수 있습니다. 왜냐하면 우리가 본문제의 답의 존재성을 확인할 때 사용했던 경로들을 본문제의 색칠과 symmetric difference 해주면 쉬운문제의 색칠과 일대일 대응이 되기 때문입니다.
따라서, 우리가 구하고자 하는 값은 쉬운 문제의 답인 $2^{|cycle basis|}$ 가 됩니다. 연결된 그래프에서 cycle basis의 개수는 $E - V + 1$ 개라는 사실도 위 글을 읽으면 알 수 있습니다.
문제를 해결하는 코드는 아래와 같습니다. 각 컴포넌트의 특성을 파악하기 위해 depth-first search를 수행하므로 시간복잡도는 $O(V + E)$ 입니다.
#include<bits/stdc++.h>
using namespace std;
const int mod = 1e8 + 7;
int N, M;
vector<int> adj[111];
int vis[111];
int cnt;
void dfs(int u) {
vis[u] = 1;
cnt++;
for(int i = 0; i < adj[u].size(); i++) {
int v = adj[u][i];
if(vis[v]) continue;
dfs(v);
}
}
int main() {
scanf("%d %d", &N, &M);
for(int i = 0; i < M; i++) {
int u, v; scanf("%d %d", &u, &v);
u--; v--;
adj[u].push_back(v);
adj[v].push_back(u);
}
int c = 0;
for(int i = 0; i < N; i++) if(!vis[i]) {
c++;
cnt = 0;
dfs(i);
if(cnt % 2) {
printf("0");
return 0;
}
}
int ans = 1;
for(int i = 0; i < M - N + c; i++) {
ans <<= 1;
ans %= mod;
}
printf("%d", ans);
}