https://www.acmicpc.net/problem/1014
https://www.acmicpc.net/problem/11014
해당 문제는 최소 버텍스 커버 문제입니다.
해당 문제에서 학생 -> 학생 의 버텍스 (엣지) 는 커닝의 가능성으로 볼 수 있습니다.
즉 모든 버텍스를 커버하면 커닝의 가능성이 있는 모든 위치를 탐색하는 것과 동일합니다.
그러므로 모든 버텍스를 커버하고 남는 자리에 학생을 앉히면 커닝을 당하거나 할 가능성이 없습니다.
해당 문제에서 특정 위치에 학생을 앉힌다고 가정하면 해당 학생과 같은 열에 있는 학생은 커닝을 당할일도 할 일도 없습니다. 즉 어떤 학생에게서 다른 학생에게 향하는 버텍스는 짝수 -> 홀수 / 홀수 -> 짝수 의 두 경우로 나뉩니다. 그러므로 해당 문제의 그래프는 홀수열 / 짝수열의 두 그룹으로 나눌 수 있는 이분그래프입니다.
이분그래프에서 최소 버텍스 문제라면
백준 1867 <돌멩이 제거> Python
https://www.acmicpc.net/problem/1867'해당 문제는 이분매칭 알고리즘을 사용하는 문제입니다.'라고 말하면 왜인지 다들 화가 날 것 같습니다. 저는 화가 났습니다. 왜냐하면 이 문제는 단순한 이분매칭
dev-diary-0717.tistory.com
해당 문제와 같은 경우로 쾨닉의 정리에 따라 문제의 해와 같은 문제를 이분매칭 했을 때의 해가 같습니다.
즉 '짝수 / 홀수 열로 나눈 이분그래프에서 이분매칭의 답을 구하면 최소 버텍스 커버의 답을 찾을 수 있고 해당 답은 앉을 수 없는 자리이므로 제외하고 다른자리에 모두 앉히면 된다' 가 되겠습니다.
짝수 -> 홀수 로 이분매칭을 했다면 짝수열에는 모두 학생이 앉을 수 있고
홀수 -> 짝수 로 이분매칭을 했다면 홀수열에는 모두 학생이 앉을 수 있으므로
전체 자리수 - 매칭 된 수 가 답이 되겠습니다.
'Coding Test > BaekJoon_Python' 카테고리의 다른 글
백준 2414 <게시판 구멍 막기> Python (1) | 2024.10.19 |
---|---|
백준 3713 <당일치기> Python (0) | 2024.10.18 |
백준 32349 <구슬 옮기기> Python (0) | 2024.10.15 |
백준 15681 <트리와 쿼리> Python (1) | 2024.10.12 |
백준 1647 <도시 분할 계획> Python (1) | 2024.10.10 |