kth990303의 코딩 블로그

이분매칭 (Bipartite Matching) Maximum Flow를 구하는 방법에는 Dinic Algorithm이 존재한다. 그런데, 모든 간선의 flow가 1이고, 이분 그래프 형태로만 존재한다면 bipartite Matching을 시도할 수 있다. (예를 들어 남녀가 미팅을 하며 각자가 원하는 짝을 1명씩 선택할 때, 최대 수로 성사시킬 수 있는 경우의 수는 이분 매칭으로 구할 수 있다.) 참고로 먼 옛적에는 Blossom Algorithm (1961)으로 최대 이분매칭 수를 O(EV^2)에 구했었다. 최악의 경우 O(V^4)까지 나올 수 있었던 셈. 원리가 궁금하다면 소멤 글을 참고해보자. https://www.secmem.org/blog/2020/04/18/Blossom/ 이분매칭의 시간복잡도..

굉장히 유명한 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/11014 11014번: 컨닝 2 최백준은 서강대학교에서 “컨닝의 기술”이라는 과목을 가르치고 있다. 이 과목은 상당히 까다롭기로 정평이 나있기 때문에, 몇몇 학생들은 시험을 보는 도중에 다른 사람의 답지를 베끼려 한 www.acmicpc.net 1014번 컨닝은 N, M 제한이 80이 아니라 10이라는 점 외엔 11014번과 동일하다. 의식의 흐름 및 해설 사실 이 문제는 너무나도 유명한 문제여서 최대유량, bitmask+dp 로 풀어야한다는 사실 자체는 알고 있었던 문제이다. 그러나 왜 최대유량으로 풀리는지 모르는 상태였기 때문였었고, 마침 우연히 최근에 flow 관련 그래프 이론을 공부중이기 때문에 ..

flow 이론에 있어서 나름 구현은 쉽지만 중요한 문제이다. 문제는 아래와 같다. https://www.acmicpc.net/problem/1867 1867번: 돌멩이 제거 첫째 줄에 n과 k가 주어진다. (1 ≤ n ≤ 500, 1 ≤ k ≤ 10,000) 이후 k개의 줄에는 돌멩이의 위치가 한 줄에 하나씩 주어진다. 줄마다 첫 번째 숫자는 행 번호, 두 번째 숫자는 열 번호를 나타낸다. www.acmicpc.net 의식의 흐름 및 해설 특정 행, 열을 최소한으로 선택하여 모든 돌멩이를 제거하는 문제이다. 행을 선택하면 그 행에 포함된 돌멩이의 열들이 영향을 받는다. 단, 다른 행들은 영향을 받지 않는다. 따라서 행과 열로 이분그래프를 나눠볼 수 있다. 여기서 돌멩이는 행-열을 연결하는 간선을 의미한다..

생긴 건 되게 bfs 처럼 생겼는데 알고보니 bfs + bipartite matching + binary_search (필수는 아니지만) 가 복합적으로 사용되는 문제였다. https://www.acmicpc.net/problem/1348 1348번: 주차장 세준 주차장은 R*C크기의 직사각형 모양이다. 세준 주차장에는 N개의 차와, M개의 주차 구역이 있다. 그리고, 모든 차는 주차 구역에 주차하려고 한다. 교통 제한 때문에, 차는 주차장의 경계와 평 www.acmicpc.net 의식의 흐름 및 해설 하나의 주차장에는 하나의 차만 들어갈 수 있고, 그 외에 이동하면서 차끼리 충돌은 고려하지 않는다. (휴... 정말 다행이다. bfs로 충분히 할 수 있겠다.) 주차장과 차끼리 연결되는 모습이 이분그래프를 ..