1574. 룩 어택

요즘은 이분 매칭 문제를 풀고 있다.

1574번: 룩 어택

---

$R \times C$ 크기의 체스판에 룩을 최대한 많이 배치하는 문제이다. 이때 룩끼리 공격 가능해서는 안 된다. 룩은 자신이 위치한 행 또는 열의 모든 칸을 공격할 수 있다. 

 

비슷한 문제로 N-Queen이 있다. 이 문제는 $N \times N$의 체스판 위에 퀸을 서로 공격할 수 없도록 최대한 많이 배치하는 문제이다. 퀸은 행과 열에 더하여 대각선까지 공격할 수 있기 때문에 특정한 형태로 모델링하기 까다롭다. 하지만 이 문제에서는 룩을 배치하기 때문에 이분 매칭으로 문제를 해결할 수 있다.

 

문제를 간단하게 하기 위해 $R \le C$라고 가정한다. 만약 $R > C$인 경우 체스판을 90도 돌려주면 된다. 체스판에는 최대 $R$개의 룩이 존재할 수 있다. $k > R$개의 룩을 배치하려고 할 경우 필연적으로 어떤 행에 룩이 두 개 이상 존재하게 되는데, 룩은 서로 공격할 수 있어서는 안 되기 때문이다(이것을 유식한 말로 비둘기집의 원리라고 한다).

 

각 행마다 룩을 배치할 열을 매칭하자. 행에서 열로 가는 유향 그래프를 만들고, 이분 매칭으로 최대한 많은 열을 매칭하면 정답을 구할 수 있다. 빈 칸에 룩을 배치할 수 없으니 주의하자.

---