백준 4207 : Infiltration

세번째로 푼 다이아문제!

 

우선 문제에서 주어진 그래프는 완전그래프! 라는 사실이 중요하다.

 

이 그래프의 특성은, 방향이 주어진다면

모든 정점에서 나가는 화살표의 갯수의 합 = 모든 그래프에서 들어오는 화살표의 갯수의 합 = 상수 라는 것이다. 이 때문에 비둘기집의 원리 사용이 가능해진다.

 

N=75 최대일 때를 생각해보자.

우리는 일단 최대한 한번에 많이 색칠을 하고싶다. 그렇기 때문에 나가는 방향의 간선이 최대인 정점을 골라서 칠해줄 것이다.

비둘기 집의 원리에 의해 최소한 하나의 정점은 37개의 다른 정점으로 뻗어나갈것이다.

-> 이게 최소가 되는 경우는 모든 정점이 37개의 간선을 받고, 모든 정점이 37개의 간선을 내보내는 균형을 이루고 있는 케이스일 것이다. 여기에서 만약 36개 정점으로 뻗게 만들려고 균형을 무너뜨리는 순간 다른 정점 하나는 38개의 정점으로 뻗어나가게 된다.(최악이 아니게 됨)

이를 통해 우리는 한번에 최소 점 38(37개 + 나 자신)개를 색칠할 수 있다.

 

38개의 점을 색칠한 이후(최악의 경우) - N=37개의 점이 남았다. 

우리는 완전그래프를 다루고있기 때문에, 이 37개의 정점만 똑 떼어놓고 보더라도 얘내도 완전그래프임을 알수 있다.

고로 위의 논리를 똑같이 적용할 수 있다.

 

37개 정점 중 최소 19개 색칠 가능,

남은 18개 정점 중 최소 10개 색칠 가능.

남은 8개의 정점 중 최소 5개 색칠 가능.

남은 3개의 정점 중 최소 2개 색칠 가능,

마지막으로 남는 하나의 정점.

 

이렇게 우리는 N이 75일 때 최대 6개의 점만 칠해도 전체를 커버할 수 있음을 증명했다.

 

이거만 알면 나머지는 구현이다.(여기서 16틀함)

 

75개 중

5개를 적절히 고르고, 만약 5개를 다 사용했는데 정점이 하나 남았다 -> 위의 답 6 케이스

5개를 적절히 고르고, 정점을 모두 사용했다 -> 답 5

4개를 적절히 고르고, 정점을 모두 사용했다 -> 답 4

...

1개를 적절히 고르고, 정점을 모두 사용했다 -> 답 1

 

속도를 빠르게 하기 위해 bitset을 사용했다.