oVeron

돌멩이 하나를 제거하기 위해서는 돌멩이가 위치한 행이나 열 중 하나를 선택해서 달리기를 해야 한다. 둘 중 하나만 택해도 된다는 점을 통해, 행 노드 따로, 열 노드 따로 분리해서 이분 그래프를 만들 수 있음을 알 수 있다. 두 노드를 연결한 간선은 두 노드를 통해 만든 좌표에 돌멩이가 존재한다는 뜻이다. 문제에서는 달리기 횟수를 최소화해서 모든 돌멩이를 수거해야 한다고 했다. 그래프에서 돌멩이는 간선이므로, 모든 간선에 대해, 간선에 속한 양 노드 중 하나를 택하되 그 수가 최소가 되게 하면 된다. 이는 곧 최소 정점 커버를 뜻하는 말이며, 최소 정점 커버는 쾨닉의 정리에 의해 최대 매칭과 동일하다고 증명되어 있으므로 이 문제는 이분 매칭으로 해결할 수 있다.#include using namespace..

알고리즘/baekjoon 2024. 7. 2. 16:50