백준 온라인 저지, 이분매칭 / 14433번: 한조대기중 (파이썬 / , 백준 플레티넘문제)

문제

그랜드마스터 승급까지 1승이 남은 욱제는 끔찍한 광경을 보고야 말았다. 팀원들이 게임을 던지기 시작한 것이다.

그렇게 승급을 포기하려던 찰나, 욱제는 적 팀도 던진다는 사실을 알아챘다! 이제 승부는 미궁 속으로 빠지게 되었다.

한 팀에는 N명의 플레이어가 있고, 각 팀원은 게임을 시작하기 전에 영웅을 한 명 선택한다. 이때 같은 팀에서 여러 명이 한 영웅을 선택할 수는 없다. 게임에는 수많은 영웅이 있고, 그 중 M개의 영웅은 게임의 승패를 결정지을 정도로 구린 영웅이다. 이런 영웅을 선택하는 것을 트롤픽이라고 불린다. (같은 게임이기 때문에 트롤픽의 수 M은 양 팀 모두 동일하다)

양 팀이 모두 게임을 던지자, 즐겜 분위기가 형성되었다. 각 팀원은 M개의 트롤픽 중 자신이 원하는 트롤픽들을 말하고, 자기 팀에서 최대한 많은 팀원이 즐겜을 할 수 있도록 트롤픽을 분배한다. 트롤픽을 하지 못한 팀원은 아쉽지만 힐러를 고르게 된다.

게임은 비슷한 실력의 팀원을 매칭시켜 주기 때문에, 결국 트롤픽을 더 적게 한 팀이 이기게 된다. 각 팀의 팀원들이 고르고 싶어하는 트롤픽의 리스트가 주어질 때, 욱제가 그랜드마스터를 찍을 수 있는지 알아보자. (비기면 점수를 안 주기 때문에 승급 할 수 없으며, 물론 욱제도 게임을 던진다)

입력

첫째 줄에 한 팀에 속한 플레이어의 수 N(1 ≤ N ≤ 300)과 트롤픽의 수 M(1 ≤ M ≤ 300), 각 팀의 팀원들이 원하는 트롤픽의 수 K1, K2(1 ≤ K1, K2 ≤ 500)가 주어진다.

다음 K1개의 줄에 걸쳐 두 수 i, j(1 ≤ i ≤ N, 1 ≤ j ≤ M)가 주어진다. 이는 욱제 팀의 i번 플레이어가 j번 트롤픽을 고르고 싶어한다는 뜻이다.

다음 K2개의 줄에 걸쳐 같은 형식으로 상대 팀의 팀원들이 원하는 트롤픽이 주어진다.

출력

승급할 수 있으면 ‘네 다음 힐딱이’를, 승급할 수 없으면 ‘그만 알아보자’를 출력한다.

제한

예제 입력 1

5 4 5 3
1 1
2 2
3 3
4 4
5 2
1 1
2 1
3 1

예제 출력 1

그만 알아보자

예제 입력 2

4 4 5 8
1 1
1 2
2 1
3 3
4 3
1 1
1 4
2 1
2 2
2 3
3 2
3 3
4 3

예제 출력 2

네 다음 힐딱이

힌트

접근 방법

- 각 팀에 대해 이분매칭을 구현한 뒤 개수를 비교해 결과를 출력한다.

코드

# https://www.acmicpc.net/problem/14433
# 접근 방법
# 각 팀에 대해 이분매칭을 구현한 뒤 개수를 비교해 결과를 출력한다.
def dfs(x):
    if visited[x]:
        return False
    visited[x] = True
    for i in team[x]:
        if not champ[i] or dfs(champ[i]):
            champ[i] = x
            return True
    return False


n, m, k1, k2 = map(int, input().split())
result = []
for k in [k1, k2]:
    champ = [[] for _ in range(m+1)]
    team = [[] for _ in range(n+1)]
    count = 0
    for _ in range(k):
        i, j = map(int, input().split())
        team[i].append(j)
    for i in range(1, n+1):
        visited = [False for _ in range(n+1)]
        if dfs(i):
            count += 1
    result.append(count)
    
if result[0] < result[1]:
    print('네 다음 힐딱이')
else:
    print('그만 알아보자')