백준 11375 열혈강호

작성일 | In |

문제 링크

  • https://www.acmicpc.net/problem/11375

알고리즘

  • 이분 매칭

깃허브 블로그 생성하고 나서 이게 첫 게시물이다. 첫 게시물이라서 어떤 문제를 고를까 생각하다가 재미있고 실생활에 유용할 것 같다는 생각에 한동안 푹 빠졌던 이분 매칭 알고리즘 문제를 선택했다.

이분 매칭은 두 개의 집합으로 나뉘어진 정점들을 각각 상대 집합의 정점에 하나씩 매칭시키는 알고리즘이다. 최대한 많은 쌍을 맺어주는 게 목표인데 원리는 다음과 같다.

A와 B 그룹으로 정점들이 분류되어 있다면, 우선 하나의 정점 집합을 기준으로 삼는다. 이 문제에서는 사원들을 기준 정점들로 삼았다. 따라서 매칭 대상 정점들이 업무이다.

  1. 먼저 첫 번째 사원부터 희망하는 업무에 맺어준다. 예를 들어서 1번 사원이 1번 업무를 희망하면 서로 매칭시키는 것이다.
    • 두 번째 사원이 희망하는 업무가 1번 업무가 아니라면 그대로 이어준다.
    • 두 번째 사원이 희망하는 업무가 1번 업무라면 첫 번째 사원이랑 희망 업무가 겹치는 상황이 발생한다. 만약 첫 번째 사원이 2번 업무도 희망하고, 2번 업무가 아직 할당되지 않았을 때는 첫 번째 사원과 2번 업무를 이어주면 된다. 따라서 1번 업무는 두 번째 사원이 맡게 된다.
  3. 이런 식으로 모든 사원들을 각각 희망하는 업무에 최대한 많이 매칭시켜주면 된다.

막상 설명하려니 힘들다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
import sys

n, m = map(int, input().split())
lst = [[]]
for i in range(n):
    lst.append(list(map(int, input().split()))[1:])
    
task = [0] * (m+1)

def sol(x):
    if visited[x]:
        return False
    
    visited[x] = 1
    
    for i in lst[x]:
        if task[i] == 0 or sol(task[i]):
            task[i] = x
            return True

    return False



for i in range(1, n+1):
    visited = [0] * (n+1)
    sol(i)
    
    
    
print(m+1 - task.count(0))