#8202 Conspiracy

재밌는 문제였다.

이 문제를 전날 자기 전부터 고민해서 일어나서 랩실을 가서 풀었는데, 핵심적인 관찰이 재밌고, 그 결과까지의 과정이 재밌는 문제였다. 추천!

 

Support Group에 사람이 포함되면 그 사람에 대응되는 정점을 선택한다고 하자.

 

관찰 1.

크기가 n인 clique가 있을 때, 그 clique에 포함되는 정점중 n-1개는 무조건 포함해야 한다.

 

관찰 1번은 나름 쉽게 떠올릴 수 있다. 

우선 문제 지문에서부터 clique를 이용해야 하기에, 당연히 떠올릴 수 있고, 만약 n-2개 이하로 포함 한다면 포함되지 않는 새로운 clique가 생겨서 모순이다. 

 

여기까지 생각한 후 생각의 전개는 다음과 같다.

1개만 교체할 수 있다면, 1개를 빼고 새로운 x개로 넣을 텐데, x가 1이라면 편하다... 근데 x가 커질수도 있는데?

우리는 교체할 때, clique에서 빠지는 정점 빼고 남아서 존재하는 n-1개의 clique내부의 정점과 새로 들어오는 정점들이 전부 연결되어 있어야 한다... 

여기서 한가지 핵심 포인트는 max clique를 찾는 것이다.

 

관찰 2

max clique에서 x가 2이상일 수가 없다. 왜냐면, 교체해버리면 다시 clique가 되는데, 따라서 max clique였다는 가정에 모순이기 때문이다.

 

따라서 정답은

1. max clique

2. max clique에서 하나 뺀거

3. max clique에서 하나 빼고 딱 하나 새로운 것 넣은 것

 

3가지이다.

이를 잘 구현해주면 되는데, 메모리랑 시간이 빡세니 ... 열심히 구현하자.