백준9522 직선 게임

작성일 | In

문제 링크

  • http://icpc.me/9522

문제 출처

  • 2013/2014 COCI #2 6번

사용 알고리즘

  • 이분 매칭

풀이

만들 수 있는 직선들을 다 그려두고, 직선을 하나씩 지우는 문제로 바꿔서 생각해봅시다.
직선을 정점으로 잡고, 교차하는 직선을 간선으로 이어주면 이분 그래프가 나옵니다.

게임은 아래와 같이 진행이 됩니다.

  1. 선공이 임의의 직선을 지운다.
  2. 후공이 임의의 직선을 지우는데, 이전 차례에 선공이 지운 직선과 교차하는 직선만 지울 수 있다.
  3. 선공이 임의의 직선을 지우는데, 이전 차례에 후공이 지운 직선과 교차하는 직선만 지울 수 있다.
  4. 반복
  5. 지울 수 있는 직선이 없으면 진다.

이분 그래프 관점에서 보면 아래와 같이 진행됩니다.

  1. L 그룹에서 정점 하나를 제거한다.
  2. R 그룹에서 정점 하나를 제거하는데, 이전 차례에 L에서 지워진 정점과 인접한 정점만 지울 수 있다.
  3. L 그룹에서 정점 하나를 제거하는데, 이전 차례에 R에서 지워진 정점과 인접한 정점만 지울 수 있다.
  4. 반복
  5. 지울 수 있는 정점이 없으면 진다.

문제의 정답부터 말하자면, perfect matching이 존재할 경우 후공이 이기고, 그렇지 않으면 선공이 이깁니다. 증명을 해봅시다.

perfect matching이 존재하는 경우

선공이 어떻게 이동을 하더라도, 후공은 항상 선공을 matching 안으로 밀어넣을 수 있습니다.
후공이 선공을 matching 안으로 계속 밀어넣으면 언젠가는 선공이 지울 수 있는 정점이 없게 되고, 후공이 이기게 됩니다.

perfect matching이 존재하지 않는 경우

선공이 후공을 matching 밖으로 쫓아낼 수 있습니다.
선공이 이기게 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <bits/stdc++.h>
#define x first
#define y second
#define all(v) v.begin(), v.end()
#define compress(v) sort(all(v)), v.erase(unique(all(v)), v.end())
using namespace std;

typedef long long ll;

int n;
int x[10101], y[10101];
int bias = 555;
vector<int> g[2020];

int par[2020], chk[2020];
int x_chk[555], y_chk[555];

int dfs(int v){
    chk[v] = 1;
    for(auto i : g[v]){
        if(chk[i]) continue; chk[i] = 1;
        if(par[i] == -1 || dfs(par[i])){
            par[i] = v; return 1;
        }
    }
    return 0;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(nullptr);
    cin >> n;
    for(int i=1; i<=n; i++){
        cin >> x[i] >> y[i];
        g[x[i]].push_back(y[i]+bias);
        x_chk[x[i]] = y_chk[y[i]] = 1;
    }
    for(int i=0; i<2020; i++) compress(g[i]);

    int match = 0;
    memset(par, -1, sizeof par);
    for(int i=1; i<=500; i++){
        memset(chk, 0, sizeof chk);
        match += dfs(i);
    }

    int a = 0, b = 0;
    for(int i=1; i<=500; i++) a += x_chk[i], b += y_chk[i];
    if(a == match && b == match) cout << "Slavko";
    else cout << "Mirko";
}