BOJ 14750번 Jerry and Tom

BOJ : https://www.acmicpc.net/problem/14750

 

과제로 이 문제를 풀게 되어서 간단하게 방법만 소개하고자 한다

 

알아야할 정보는 다음과 같다

 

1. N K H M 순으로 인풋이 주어진다

2. N개만큼 다각형의 좌표가 주어진다(반시계방향)

3. H개만큼 홀의 갯수가 주어진다

4. M개만큼 쥐의 마리수가 주어진다

5. 각 홀은 최대 K마리의 쥐가 숨을 수 있다

6. 각 쥐는 당장 시야에 보이는 홀에만 들어갈 수 있다

   조건으로는 쥐와 홀에 대해서 선을 그엇을때 다른 벽이나 모서리와 겹치지 않아야한다.

7. 각 쥐는 반드시 다각형 내부에 존재한다 -> 다각형 선분위에 존재하지 않는다

8. 각 홀은 반드시 벽(선분)에 존재한다

9. 두개이상의 홀이나 쥐가 같은 위치에 존재하지 않는다

 

이때 모든 쥐가 숨을 수 있나 없나를 묻는 문제로,

문제를 해결하기 위해 필요한 지식은 

선분 교차확인법, 이분매칭 이렇게 2가지이다.

 

쥐와 홀의 쌍에 대해서 모든 벽과 선분교차를 확인하여

쥐가 들어갈 수 있는 홀을 따로 찾아둔 후에,

이분매칭을 통해서 쥐가 최대로 숨을 수 있는 마리수를 찾는다.

이때 이분매칭의 값이 쥐의 마리수와 같다면 possible이 된다