백준 9208번 풀이 (링월드)

문제 링크: https://www.acmicpc.net/problem/9208

9208번: 링월드

 

풀이)

일단 그래프 모델링을 해봅시다. 이분그래프 G = (A, B)를 생각할건데, |A| = N, |B| = M이고, i번째 구간이 [j, k]일 때, A에서 i번째 점을 B에서 [j, k] 점들과 연결합시다. 이렇게 하면 문제가 "그래프 G에서 A를 덮는 매칭이 존재하는가?"로 변하게 됩니다.

이 상태로 segment tree를 이용하여 문제를 해결할수도 있지만, 제한이 커서 시간초과가 날 가능성이 높습니다. 그렇기 때문에 다른 풀이를 찾아볼겁니다.

 

새로운 이분그래프 H = (C, D)를 생각해봅시다. 초기에 |C| = N, |D| = M*2이고, H에 존재하는 간선은 없습니다. 1부터 N번째 구간에 대해, 간선과 점을 다음 방식으로 적절히 추가하겠습니다.

 

i번째 구간이 [j, k]일 때

1. j<=k인 경우: C에서 점 i와 D에서 구간 [j, k]를 잇는 간선을 추가해주고, C에 새로운 점 v를 추가한 다음 v와 D에서 구간 [j+M, k+M]을 잇는 간선을 추가한다.

2. j>k인 경우: C에서 점 i와 D에서 구간 [j, k+M]을 잇는 간선을 추가한다.

 

이때, 다음 명제가 성립합니다.

"M>=N일 때, G에서 A를 덮는 매칭이 존재할 필요충분조건은 H에서 C를 덮는 매칭이 존재하는 것이다."

 

증명)

G에서 A를 덮는 매칭이 존재할 경우, H에서 C를 덮는 매칭이 존재함은 자명합니다. (G와 동일하게 연결)

G에서 A를 덮는 매칭이 존재하지 않을 경우, H에서 C를 덮는 매칭이 존재하지 않음을 보입시다.

 

Lemma) G에서 A를 덮는 매칭이 존재하지 않는다면, A의 어떤 부분집합 S가 존재하여, N(S)가 B의 진부분구간이 되면서 |S|>|N(S)|를 만족한다. (즉, N(S)가 구간 [j, k]꼴이 되게 할 수 있다.)

 

Lemma의 증명)

홀의 결혼정리에 의해, A의 어떤 부분집합 S가 존재하여 |S|>|N(S)|를 만족합니다. 이때, N(S)가 진부분구간이 아니라면, N(S)를 진부분구간들로 분할한 후, 비둘기집의 원리에 의해 이 중 진부분구간을 적절히 선택하면 Lemma를 만족하는 진부분구간을 선택하는 것이 가능합니다.

 

Lemma를 만족하는 진부분구간 N(S) = [j, k]를 선택합시다.

Case 1) j<=k인 경우

그래프 H에서 동일하게 S를 C에서 선택해주면, |S|>|N(S)|를 만족하고, 홀의 결혼정리에 의해 H에서 C를 덮는 매칭이 존재하지 않습니다.

Case 2) j>k인 경우

C의 부분집합 S'을 다음과 같은 방식으로 고릅시다.

1. S의 원소 v에 대해, N(v)가 [x, y] (x<=y<=k)라면, S'에 N(u) = [x+M, y+M]을 만족하는 점 u를 추가한다.

2. 나머지 경우, S에 점 v를 그대로 추가한다.

이 방식으로 S'을 고르면, N(S') = [j, k+M]이 되고, |S|=|S'|이므로, |S'|>|N(S')|이 되어 홀의 결혼정리에 의해 H에서 C를 덮는 매칭이 존재하지 않습니다.

 

따라서, 증명이 완료되었습니다.

 

위 증명에 의해, 문제를 원형에서 직선으로 바꿀 수 있게 되었습니다.

직선형에서는 다음과 같은 그리디 알고리즘을 통해 문제를 쉽게 해결할 수 있습니다.

 

1. 정점 1에서 시작한다.

2. 현재 정점이 i일 때, 매칭이 안 된 [x, y]구간 중 (단, x<=i) y가 최소인 구간을 고른다.

3-1. y<i일 경우, 매칭이 불가능. -> NO 출력

3-2. y>=i인 경우, 구간 [x, y]를 매칭해주고 i에 1을 더해준다음 2로 돌아가서 반복한다.

4. 마지막에 매칭이 안 된 구간이 존재하면 NO, 그렇지 않으면 YES 출력

 

위 알고리즘은 쉽게 증명할 수 있으니 증명은 독자 여러분께 맡기도록 하겠습니다.

 

구현: (N, M이 글과 반대로 되어있습니다.)

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;

void solve(){
    int n, m;
    scanf("%d %d", &n, &m);
    vector<pair<int, int>> v;
    for (int i=0;i<m;i++){
        int x, y;
        scanf("%d %d", &x, &y);
        if (x<=y){
            v.emplace_back(x, y);
            v.emplace_back(x+n, y+n);
        }
        else v.emplace_back(x, y+n);
    }
    sort(v.begin(), v.end());
    priority_queue<int, vector<int>, greater<int>> pq;
    int pt = 0;
    for (;pt<(int)v.size();){
        int y = v[pt].first;
        pq.push(v[pt].second);
        for (pt++;pt<(int)v.size();pt++){
            if (v[pt].first!=v[pt-1].first) break;
            pq.push(v[pt].second);
        }
        int x = n*2;
        if (pt<(int)v.size()) x = v[pt].first;
        for (int i=0;i<x-y && !pq.empty();i++){
            if (pq.top()<y+i){
                printf("NO\n"); return;
            }
            pq.pop();
        }
    }
    if (pq.empty() && n>=m) printf("YES\n");
    else printf("NO\n");
}

int main(){
    int t;
    scanf("%d", &t);
    while(t--){
        solve();
    }
    return 0;
}

 

참고) 초기에 M>=N 조건을 확인하지 않으면 다음과 같은 반례가 존재합니다.

3 4

1 3

2 1

2 1

3 2