[백준 11375번] 파이썬 - 열혈강호

백준 11375 - 열혈강호

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

# 조건

• 강호네 회사에는 직원이 N명이 있고, 해야할 일이 M개가 있다.
• 직원은 1번부터 N번까지 번호가 매겨져 있고, 일은 1번부터 M번까지 번호가 매겨져 있다.
• 각 직원은 한 개의 일만 할 수 있고, 각각의 일을 담당하는 사람은 1명이어야 한다.
  0 각각의 직원이 할 수 있는 일의 목록이 주어졌을 때, M개의 일 중에서 최대 몇 개를 할 수 있는지 구하는 프로그램을 작성하시오.

입력

• 첫째 줄에 직원의 수 N과 일의 개수 M이 주어진다. (1 ≤ N, M ≤ 1,000)
• 둘째 줄부터 N개의 줄의 i번째 줄에는 i번 직원이 할 수 있는 일의 개수와 할 수 있는 일의 번호가 주어진다.

출력

• 첫째 줄에 강호네 회사에서 할 수 있는 일의 개수를 출력한다.

# 접근 방법

• 직원의 그룹에서 일의 그룹에 최대한 많은 매칭을 시켜야된다.
• 따라서, 이분 매칭을 이용하여 풀어준다.
• 서로 매칭된 결과를 기록할 connect 리스트를 일의 개수와 같은 크기로 만들어 준다.
• 이후, 모든 직원을 순회하면서 탐색해준다.
  • 현재 직원을 이분 매칭하며 방문 체크를 해줄 visited 배열을 생성한 후 이분 매칭을 시작한다.
• 현재 직원이 할 수 있는 일의 리스트를 순회하며
  • 이번 턴에 방문하지 않았다면 True로 방문 표시 해준 후 아래 조건을 확인한다.
  • 지금 이 일에 어떠한 직원도 배정되지 않았거나, 이미 배정되어 있는 직원이 맡을 수 있는 다른 일이 있다면 지금 직원을 현재 일에 배정해 준다.
• 만약 어떤 일에도 배정하지 못한다면 return 0을 해준다.

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

def bipartite_matching(num):  
    for work in workers[num]:  
        if visited[work] == False:  
            visited[work] = True  
            if not connect[work] or bipartite_matching(connect[work]):  
                connect[work] = num  
                return 1  

    return 0  

N, M = map(int, input().split())  

workers = [[]]  
for _ in range(N):  
    query = [*map(int, input().split())]  
    workers.append(query[1:])  

result = 0  
connect = [0] * (M+1)  

for i in range(1, N+1):  
    visited = [False] * (M+1)  
    bipartite_matching(i)  

print(M - connect.count(0) + 1)

• 위의 코드보다 10배이상 빠르게 돌아가는 로직이 있었다.
• 똑같은 이분 매칭이지만, 우선 비어있는지를 체크해주고 비어있는 곳이 없다면 이미 배정된 직원을 옮기게 로직을 변경해주었다.

def bipartite_matching(num):  
    for work in workers[num]:  
        if not connect[work]:  
            connect[work] = num  
            return 1  
    for work in workers[num]:  
        if visited[work]:  
            continue  
        visited[work] = True  
        if bipartite_matching(connect[work]):  
            connect[work] = num  
            return 1  

    return 0

 

• 항상 맞췄다고 넘어가는 것이 아니라, 조금 더 효율적으로 사용할 방법이 없는지 고민해보는 것이 중요한 것 같다.