한동안 알고리즘 공부를 멈췄다가 최근에 다시 흥미가 생겨 발을 들이기 시작했다. 이번에는 또 어떤 씹덕 알고리즘을 배워볼까 하다가 이분 매칭이 맛있어 보였다.
모든 간선 용량이 1이고, 정점을 두 개의 그룹으로 나누었을 때, 존재하는 모든 간선의 양 끝 정점이 서로 다른 그룹에 속하는 형태의 유량 그래프를 이분 그래프(bipartite graph)라고 한다.
이분 그래프에서 한쪽 그룹을 A, 다른 쪽 그룹을 B라고 할 때, 간선의 방향이 모두 A -> B일 때, 최대 유량을 구하는 문제를 이분 매칭(bipartite matching) 문제라고 부른다. 위 그림에서는 생략되었지만 소스에서 A로 가는 간선과 B에서 싱크로 가는 간선이 있다고 생각하면 된다.
이분 그래프에서 매칭은 두 그룹의 정점을 잇는 간선을 말하는데, 이때 각 정점은 한 번까지만 선택될 수 있다. 위 그래프에서 (A, 2)와 (A, 5)는 동시에 매칭될 수 없다. A가 두 번 선택되었기 때문이다.
알고리즘 동작 과정을 차근차근 살펴보자.
정점은 A 그룹을 순차적으로 돌면서 아직 매칭이 안 된 친구들이 있으면 매칭을 시도한다. 제일 처음에는 (A, 2)와 매칭된다. 그 다음 B의 인접 원소가 {2, 3, 4}인데, 이 원소도 순차적으로 훑는다. 2와 매칭하려는데 2는 이미 A와 매칭되어 있다. 이 경우에는 A를 다른 원소와 매칭시킬수 있는지 찾은 다음 다른 원소와 매칭시킬 수 있다면 그녀석과 매칭시키고 자기가 뺏는다. 그래서 매칭 (A, 2)는 사라지고, 새로운 매칭 (B, 2)와 (A, 5)가 생긴다. C는 곧바로 1과 매칭시켜 (C, 1)을 얻는다. D는 인접 원소가 {1, 2, 5} 이고 제일 먼저 1을 건드리는데 이 녀석은 C와 매칭되어 있었다. C는 쫒겨나고 5를 찾아간다. 5는 A와 매칭된 상태였는데, A는 쫒겨나고 2로 간다. A가 2로 갔더니 B와 매칭된 상태였고 B를 3으로 쫒아낸다. 그래서 (C, 1)이 소거되고 (C, 5)가 생겼으며, (A, 5)가 없어지고 (A, 2)가 되었으며, (B, 2)는 사라지고 (B, 3)이 되었다.
E의 경우 다른 녀석들을 쫒아내도 다른 원소와 매칭시키는 것이 불가하다. 때문에 위 그래프에서 최대 매칭은 4이다. (A, 2), (B, 3), (C, 5), (D, 1)
1017번: 소수 쌍
boj.ma
수들이 주어졌을 때 모든 수들의 쌍의 합을 소수로 만들 때, 첫번째 원소와 짝지을 수 있는 수들을 구하는 문제이다. 소수의 특징을 이용해 이분 그래프 뚝딱 만들고 이분 매칭으로 쇽쇽 해결하면 되는 문제이다. 아이디어가 재미있었던 문제이다.
백준 단계별로 풀어보기에서 이분 매칭 문제들 파이썬으로 맞힌 사람 중 수행 시간 1등먹기 하고 있다. (언제깨질진 모르겠지만...ㅎ)
'Computer Science > 알고리즘' 카테고리의 다른 글
| [알고리즘] 비트 연산 (1) | 2024.02.04 |
|---|---|
| [알고리즘] KMP 알고리즘 (0) | 2023.09.15 |
| [알고리즘] 서로소 집합 알고리즘 (Union-Find) (0) | 2022.09.23 |
| [알고리즘] 플로이드 워셜 (0) | 2022.08.30 |
| [알고리즘] 데이크스트라 최단 경로 알고리즘 (0) | 2022.08.06 |