[Python 3] BOJ 11375: 열혈강호

 

이분 매칭 알고리즘을 사용한다.

이분 매칭 (Bipartite Graph)는 두 개의 겹치지 않는 정점의 집합으로 나타낼 수 있는 그래프다. 이 두 집합을 왼쪽 집합이랑 오른쪽 집합으로 정의한다. 이 때, 이분 매칭은 왼쪽 집합의 각 정점을 오른쪽 집합의 정점과 연결하되, 한 정점은 최대 한 번만 매칭을 해야 한다. 

예를 들어보자.

왼쪽 집합 = {A,B,C,D}

오른쪽 집합 = {1,2,3}

<연결 관계>

A= (1,2)

B=(1)

C=(2,3)

D=(3)

 

<최대 매칭 찾기>

1. A는 1과 2와 매칭될 수 있다. A를 1과 매칭시킨다.

2. B는 1과 매칭될 수 있는데, 이미 A와 매칭이 되어있다. 

따라서 A를 2로 옮기고, B를 1과 매칭시킨다.

3. C는 2와 3과 매칭될 수 있다. A는 2와 매칭되어 있으므로, C를 3과 매칭시킨다.

4. D는 3과 매칭될 수 있다. 하지만, C가 이미 3과 매칭되어있지만,

C를 다른 곳으로 옮길 수 없으므로, D는 매칭되지 않는다.

 

최종 연결 A - 2, B -1 , C -3

 

import sys
sys.setrecursionlimit(int(1e5))
n,m=map(int,input().split())
data=list(list(map(int,input().split()))[1:] for _ in range(n))

def dfs(x):
    for i in data[x]:
        if not check[i]:
            check[i]=1
            if visited[i]==-1 or dfs(visited[i]):
                visited[i]=x
                return 1
    return 0

visited=[-1 for _ in range(m+1)]
answer=0
for i in range(n):
    check=[0 for _ in range(m+1)]
    if dfs(i):
        answer+=1

print(answer)

 

check는 현재 DFS를 이용하여 탐색할 때, 오른쪽 집합의 정점 i가 방문이 되었는지에 대한 여부를 기록한다.

visited는 정점의 현재 연결 관계를 저장한다.