[백준 2188번] 파이썬 - 축사 배정

백준 2188 - 축사 배정

시간 제한 2초, 메모리 제한 128MB

# 조건

• 농부 존은 소 축사를 완성하였다.
• 축사 환경을 쾌적하게 유지하기 위해서, 존은 축사를 M개의 칸으로 구분하고, 한 칸에는 최대 한 마리의 소만 들어가게 계획했다.
• 첫 주에는 소를 임의 배정해서 축사를 운영했으나, 곧 문제가 발생하게 되었다.
• 바로 소가 자신이 희망하는 몇 개의 축사 외에는 들어가기를 거부하는 것이다.
• 농부 존을 도와 최대한 많은 수의 소가 축사에 들어갈 수 있도록 하는 프로그램을 작성하시오.
• 축사의 번호는 1부터 M까지 매겨져 있다.

입력

• 첫째 줄에 소의 수 N과 축사의 수 M이 주어진다. (1 ≤ N, M ≤ 200)
• 둘째 줄부터 N개의 줄에는 각 소가 들어가기 원하는 축사에 대한 정보가 주어진다.
• i번째 소가 들어가기 원하는 축사의 수 Si (0 ≤ Si ≤ M)이 먼저 주어지고, 이후 Si개의 축사 번호가 주어진다.
• 같은 축사 번호가 두 번 이상 주어지는 경우는 없다.

출력

• 첫째 줄에 축사에 들어갈 수 있는 소의 최댓값을 출력한다.

# 접근 방법

• 각 축사 마다 최대 한 마리가 들어 갈 수 있으며 이 때, 최대로 많은 소를 넣어야 하기 때문에
  • 문제를 읽으며 바로 이분 매칭으로 풀 수 있겠구나 생각하였다.
• 각 소의 번호 0~N-1을 인덱스로 활용하여 cows 2차원 리스트를 사용해준다.
  • 각 소가 희망하는 축사번호를 소에 알맞는 인덱스에 넣어준다.
• 이분 매칭을 사용하기 위하여 Bipartite Matching 함수를 만들어주고, 소와 축사의 매칭을 기록할 connect 리스트와 현재 소를 매칭해주며 방문한 축사인지를 기록할 visited 리스트를 사용해준다.
• 0번 소부터 N-1번 소까지 순회하며 이분 매칭을 시켜준다.
  • 현재의 소가 희망하는 축사들을 순회하며 현재 턴에 방문하지 않은 경우 방문 표시를 해주고 아래 dfs를 수행한다.
  • 현재 배정하고자 하는 축사에 다른 소가 없거나, 다른 소가 있지만 다른 소가 옮길 수 있는 축사가 있다면 옮겨준다.
  • 그렇지 않은 경우 넘어가주고 현재 소를 아무 축사에도 배정하지 못하였다면 return 0를 해준다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

def bipartite_matching(num):  
    # 현재 소가 희망하는 축사를 순회  
    for val in cows[num]:  
        # 이번턴에 방문하지 않았다면  
        if not visited[val]:  
            visited[val] = True  
            # 축사에 다른 소가 없거나, 다른 소가 이동가능하면  
            # 현재 소를 배정해주고 return 1            
            if connect[val] == -1 or bipartite_matching(connect[val]):  
                connect[val] = num  
                return 1  

    # 현재 소가 아무데도 배정 못햇다면 return 0  
    return 0  


N, M = map(int, input().split())  
cows = [[] for _ in range(N)]  

# 소가 희망하는 축사 넣어주기  
for i in range(N):  
    want = [*map(int, input().split())]  
    for j in range(1, want[0]+1):  
        cows[i].append(want[j]-1)  

# 소와 축사 매칭 기록  
# 축사에 넣는 것이므로 축사 크기만큼  
connect = [-1] * M  

for i in range(N):  
    # 현재 소를 배정하면서 축사를 방문햇는지 여부  
    # 마찬가지로 축사 크기    
    visited = [False] * M  
    bipartite_matching(i)  

result = 0  
for i in connect:  
    if i != -1:  
        result += 1  

print(result)