문제 링크 https://www.acmicpc.net/problem/1867 문제 요약 \(N*N\)격자판위에 돌맹이들이 놓여져 있다. 한번의 작업으로 한개의 행이나 한개의 열에 있는 돌멩이를 모두 제거할 수 있다. 이 때 최소 몇번의 작업을 해야 격자판 위에 있는 돌멩이를 모두 제거할 수 있는지 구하는 문제다. 문제 풀이 처음 이 문제를 본다면 \(greedy\)로 접근을 하기 쉽다. 하지만 그렇게 접근을 시작하는 순간 문제는 미궁으로 빠지게 된다. 그렇다면 어떻게 접근을 해야할까? 우선 아래와 같은 격자판이 있다고 가정을 해보자. 위 격자판을 그래프로 생각해보자. 정점은 각각의 열과 행이고 돌멩이가 있는 칸은 열과 행을 잇는 간선이라고 생각을 한다. 그렇다면 그래프는 아래와 같이 그려진다. 만약에 \..
