백준 28090 - 특별한 한붓그리기 (C++)

문제

• 문제 링크

  
   BOJ 28090 - 특별한 한붓그리기 
  

• 문제 요약

각각 $N$개의 정점으로 구성된 집합 $A$, $B$가 있고, 두 집합은 이분 그래프의 형태로 연결되어 있다.
이제 뉴비와 고인물이 문제에 정의된 규칙대로 게임을 진행하려 한다.
서로 최선의 전략으로 게임을 진행할 때, 결국 승리하게 되는 쪽을 판단해보자.

• 제한

TL : $2$ sec, ML : $1024$ MB




$1 ≤ N ≤ 450$

$1 ≤ L ≤ min(N^2, 2,000)$

중복된 간선은 주어지지 않는다.

알고리즘 분류

• 게임 이론(game_theory)
• 최대 유량(maximum_flow)
• 이분 매칭(bipartite_matching)

풀이

뉴비가 선공을 함에 따라, 뉴비가 이길 수밖에 없는 상황을 생각해 보자.

이떤 정점 $A_i$에 대해, $B → A_i$ 로 연결시킬 수 있는 정점이 없다면 뉴비가 반드시 승리한다.

그럼 반대로 질 수밖에 없는 상황은?

두 집합 간 최대 매칭 수를 계산해보자.
만약 모든 $A_i$가 $B_j$에 매칭될 수 있다면, 뉴비가 뭘 고르던 $B$에서부터 대응이 가능하기 때문에 뉴비는 반드시 패배한다.

---

집합 간 최대 매칭 수는

$1 ≤ N ≤ 450$이고,

이분 그래프의 형태를 띠며

정점 당 $1$번만 선택될 수 있으므로

이분 매칭을 통해 $O(VE)$만에 계산할 수 있다.

앞서 말했듯이, 최대 매칭 수가

$n$보다 작다면 뉴비를 승리의 길로 이끌 정점이 반드시 하나 이상 존재한다.

$n$과 같다면 고인물은 어떤 $A_i$에도 대응할 수 있다.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
vector <int> Gr[455];
int n, l, r, B[455], Visit[455];
 
bool f(int p)
{
    for (int& i : Gr[p])
        if (!Visit[i])
            if (Visit[i] = 1; !B[i] || f(B[i]))
                return B[i] = p;
    return 0;
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin >> n >> l;
    for (int i, j; l--;)
    {
        cin >> i >> j;
        Gr[i].push_back(j);
    }
 
    for (int i(1); i <= n; r += f(i++))
        memset(Visit, 0, sizeof Visit);
 
    cout << (r < n ? "Newbie" : "Oldbie");
}

comment

끝