오랜만에 적어보는 벨로그..
오늘은 이분 매칭에 대해서 적어보고자 한다.
이분 매칭은 A, B로 나뉜 이분 그래프에서 A에서 B로 이동하는 최대 유량... 어쩌구... 는 모르겠고, 그래프에서 정점들의 집합을 두개로 나눴을 때, 한 집합의 정점에서 다른 정점의 집합으로 1:1(혹은 1: M)으로 중복되지 않게 연결할 수 있는 최대 간선 개수 정도라고하면 되려나..
아무튼 대충 그림으로 설명하면
이런 이분 그래프가 있을 때,
이렇게 겹치지 않게 정점들을 매칭할 때, 만들 수 있는 최대 간선 수라고 보면 될 거 같다.
과정
왼쪽 정점들을 순회하면서 연결할 수 있는 정점들을 DFS로 탐색한다.
먼저, A가 연결 가능한 정점들을 순회한다. 2번 정점을 확인하고 2번 정점에 이미 연결된 정점이 없으니까 A는 2번 정점을 선택한다.
다음으로 B가 연결 가능한 정점들을 순회한다. 처음에 2번 정점을 확인하는데, 2번 정점은 이미 A가 선택했다. 이 때, A가 다른 정점을 선택할 수 있는지 다시 확인한다. A는 5번 정점과 연결 가능하고, 5번 정점은 연결된 정점이 없으니, A는 5번 정점을 선택한다. 그리고 A가 다시 정점을 선택했으니 다시 B로 돌아온다. 그리고 2번 정점을 선택한다.
다음 C를 확인해보면 1번 정점과 연결된 정점이 없으니까 1번 정점을 선택한다.
D가 가능한 정점을 순회하면 먼저 1번 정점을 확인한다. 1번 정점엔 C가 연결되어 있는데, C가 가능한 정점을 확인한다. 5번 정점을 확인하면, A가 이미 연결되어 있고 다시 A가 가능한 정점을 확인한다. A는 더 이상 연결할 수 있는 정점이 없으니 그대로 유지한다. C도 더 이상 연결할 수 있는 정점이 없으니 D로 돌아온다. 다음에는 2번 정점을 확인한다. 2번 정점에 이미 B가 연결되어 있으니까 B가 가능한 정점을 확인하고, B는 3번 정점이 가능하니까 3번 정점을 선택한다(그림에 왜 4번 정점이라고 해놨지.. 3번 정점..). 그러면 D가 2번 정점을 선택한다.
마지막으로 E는 2번 정점만 가능하므로 2번 정점만 확인하는데, 이미 D가 2번 정점에 연결되어 있으니 D를 다시 확인한다. D는 5번 정점이 가능하지만 5번 정점은 A가 이미 선택했으므로 다른 가능한 정점이 없고, E는 선택할 수 있는 정점이 없게된다.
이렇게 위와 같은 그래프는 총 4개의 간선을 만들 수 있다.
코드
# 왼쪽 정점수, 오른쪽 정점 수
n, m = 5, 5
# 왼쪽 정점에서 연결 가능한 오른쪽 정점 번호들
graph = [[2, 5], [2, 3, 4], [1, 5], [1, 2, 5], [2]]
# 선택된 정점 번호
selected = [-1] * (m + 1)대충 위의 그래프를 이렇게 만들어 두고,
for i in range(n):
visited = [False] * (n)
bimatch(i)각 정점들을 순회하며 bimatch함수를 호출해주자.
visited 배열은 이미 확인한 왼쪽 정점들을 다시 확인하지 않기 위함이다.
def bimatch(N):
if visited[N]:
return False
visited[N] = True
for num in graph[N]:
if selected[num] == -1 or bimatch(selected[num]):
selected[num] = N
return True
return False if문 내에서 bimatch함수를 재호출하면서 DFS로 가능한 정점을 탐색한다.
result = 0
for i in range(1, m+1):
if selected[i] >= 0:
result += 1 마지막으로 선택된 정점들의 개수를 세면 끝!
백준에는 대표적인 이분 매칭 문제들이..
2188번 축사배정
이랑
열혈강호 시리즈들...은 풀만한 거 같다.
알고리즘마다 기본 난이도가 있다고 하는데, 이분 매칭은 기본 난이도가 플래티넘4로 기준이 맞춰져 있는 거 같다. 다 플래4 이상인 듯..?
