[백준 14433] 한조 대기 중(python)

https://www.acmicpc.net/problem/14433

14433번: 한조 대기 중

한조 대기 중 문제

트롤 픽에 따라 욱제가 이길 수 있는지 없는지 확인하는 문제

 

#사용 알고리즘

이분 매칭

 

📌문제 접근 포인트

※ 문제 자체는 이분 매칭 알고리즘 구현 방법만 알면 쉽게 해결 할 수 있는 문제
1. 배정할 수 있는 트롤픽 수를 구하기 위한 방법을 생각해보자. 각각의 고를 수 있는 트롤픽의 경우를 찾기 위해서 이분 매칭 알고리즘을 생각해볼 수 있다.

2. K1에 대한 케이스와 K2에 대한 케이스 각각을 만들어 준 후 각각의 케이스에 대해 이분 매칭 알고리즘을 진행했을 때 결과 값을 비교해보자. 비교에 따라 요구 출력대로 출력하면 성공

⚙ 내가 푼 정답 코드

def find(n):
    if visited[n]:
        return False
    visited[n] = 1
    for i in team[n]:
        if not troll[i] or find(troll[i]):
            troll[i] = n
            return True
    return False

import sys
N, M, K1, K2 = map(int, sys.stdin.readline().split()) # 사람, 트롤, 트롤수들
result = []
for case in (K1, K2): # K1, K2개의 팀에 해당하는 케이스
    team = [[] for _ in range(N+1)]
    troll = [0]*(M+1)
    for _ in range(case):
        i, j = map(int, sys.stdin.readline().split())
        team[i].append(j)

    cnt = 0
    for i in range(1, N+1):
        visited = [0] * (N+1)
        if find(i):
            cnt += 1
    result.append(cnt)
    
if result[0] < result[1]: # 이길 수 있으면
    print('네 다음 힐딱이')
else:
    print('그만 알아보자')