(최소 정점 커버) = (최대 매칭)
[최소 정점 커버]
위 그림처럼 정점에 색칠을 하면 인접한 간선들이 색칠될 때,
최소한의 정점만 색칠하여 모든 간선을 색칠하는 것.
[쾨닉의 정리]
https://kangwlgns.tistory.com/120
위 링크에서 상어의 저녁식사를 푸는 스킬에 대해 설명했었습니다.
쾨닉의 정리에서도 해당 스킬을 사용한다고 볼 수 있습니다.
위 링크에 자세한 설명을 적었지만 여기서 간단하게 설명하자면,
우선 이분 매칭으로 최대 매칭을 구하고, 후에 생각을 끼워 맞추는 겁니다.
최소 정점 커버에 사용한 것과 같은 그래프입니다.
위 그래프를 최대 매칭하면 위 그림과 같습니다. (다르게 나올 수도 있습니다.)
최소 정점 커버가 최소한의 정점만 색칠하여 간선을 색칠하는 것이라고 했었습니다.
그리고 이분 매칭은 간선으로 연결가능한 두 정점 그룹에 대해 빠짐없이 서로를 매칭해 주는 것입니다.
간선을 중심으로 생각해보면,
이분 매칭으로 최대 매칭을 구하면 더 이상 연결될 간선이 없다는 의미이고,
현재 매칭된 간선의 양 끝 정점만으로 모든 간선을 색칠할 수 있게 됩니다.
그런데 과연 이렇게 색칠할 필요가 있을까요?
하나의 간선에는 두 개의 정점이 붙어있고... 위 간선을 색칠한 B그림에서는 필요 이상으로 색칠한 것을 볼 수 있습니다.
이제 여기서 생각을 끼워 맞춰 보겠습니다.
조금만 생각해보면
어차피 이분 그래프에서 매칭된 간선은 무조건 양쪽에 정점을 갖고 있으므로, 잘만 칠하면 양쪽 정점을 다 칠할 필요 없이 하나의 정점만 칠해도 모든 간선을 커버할 수 있다는 걸 알 수 있습니다.
그리고 우리가 따로 잘 칠해줄 필요 없이 우리는 생각만 끼워 맞추면 됩니다.
이분 매칭으로 정점 쌍을 구하고 어딘가에는 색칠을 잘 해서 모든 간선들을 커버했겠구나.
즉, (최대 매칭) = (최소 정점 커버)임을 알 수 있습니다.
[BOJ 1876 - 돌멩이 제거]
https://www.acmicpc.net/problem/1867
위의 개념을 가지고 해당 문제를 풀어보겠습니다.
위 문제의 예시로 위와 같은 경우가 있다고 생각해보면,
돌멩이 ㄱ을 줍기 위해서는 a행 혹은 1열로 줍는 방법이 있습니다. 마찬가지로 ㄴ은 a행과 3열 ... 이렇게 진행해서 최종적으로 ㅂ은 d행과 1열입니다.
이를 그래프로 도식화하면 아래와 같습니다.
주워야 하는 돌멩이들이 ㄱ, ㄴ, ㄷ, ㄹ, ㅁ, ㅂ, ㅅ이고 최소한의 방법으로 이들을 모두 주워야 합니다.
그런데 하나의 돌멩이가 서로 다른 정점 그룹에 해당하는 정점들과 딱 하나만 인접해 있으므로 아래 그림과 같이 바꿀 수 있습니다.
각 돌멩이들의 정보가 간선이 됐으므로 이 문제는 최소한의 방법으로 모든 간선을 커버하는 문제가 됐고,
결국 최소한의 정점만 색칠하여 간선을 모두 색칠하는 문제입니다.
이분 매칭으로 답을 구하면 됩니다.
'정리 > 알고리즘' 카테고리의 다른 글
| [알고리즘] 정점 선인장 (0) | 2023.09.23 |
|---|---|
| [알고리즘] 이분매칭 (0) | 2023.03.20 |
| [알고리즘] 마나허 (Manacher) (0) | 2023.02.26 |
| [알고리즘] KMP (0) | 2023.02.05 |
| [알고리즘] 이분 탐색 (Binary Search) (0) | 2023.01.15 |
