https://www.acmicpc.net/problem/1867이분매칭 알고리즘을 사용하는 문제입니다. 정확하게는 이 문제는 단순한 이분매칭 문제가 아닌 '최소 버텍스 커버(Minimum Vertex Cover)' 문제입니다. 최소 버텍스 커버란 무엇인지 먼저 짚고 넘어가겠습니다.어떠한 그래프가 있습니다.해당 그래프에서 몇 개의 정점을 고르겠습니다. 과연 몇 개의 정점을 골라야 그래프에 존재하는 모든 간선이 고른 정점과 연결되어 있을까요?해당 문제의 답을 찾는 것이 바로 최소 버텍스 커버 문제입니다. 그렇다면 문제는 왜 최소 버텍스 커버 문제일까요?행과 열을 나누어 각각 노드 그룹으로 쪼갠 뒤 돌이 있는 위치의 행 노드와 열 노드를 연결해 그래프를 만든다면 각 간선의 양 끝중 하나의 정점만 선택되어도..
