[백준 1765] 닭싸움 팀 정하기

[ 백준 1765 : 닭싸움 팀 정하기 ]


조금 억지스럽게 푼것같은 문제
처음에 문제를 어떻게 풀어야 할지 계속 생각하다가 그냥 완탐으로 풀었다.
문제는 재귀로 풀까 반복문으로 풀까 망설이다가 그냥 큐로 풀었다.

문제가 좀 간단한데 해석하는데 좀 걸렸다. 요즘엔 한국어도 해석이 어렵다...
무튼
F로 나온 사람들은 일단 모두 같은 팀이다.
E인 사람은 그러니까, 원수의 원수는 같은팀이고 이 사람의 친구들도 같은팀이다.
이렇게 생각하면 쉽게 풀리는데

1. 일단 로직은 원수인 사이들을 모두 벡터(E)에 넣고 친구인 사이를 모두 벡터에 집어넣는다(F).
2. 사람 1번부터 N번까지 탐색을 할텐데 만약 현재 살펴봐야할 사람이 이미 팀에 소속되어 있으면 그냥 건너 뛴다.
3. 만약 아무 팀에도 들어가 있지 않는다면 현재 만들어진 팀+1 팀에 들어간다. 그리고 BFS를 돈다.
4. 일단 이 사람 (X) 의 친구들의 친구들 무튼 친구랑 친구관계인 사람들은 모두 내 팀이니 전부 같은 팀으로 넣는다.
5. 원수인 사람은 일단 큐에 집어넣고 첫번째 원수로 표시를 해준다.
6. 첫번째 원수의 원수들(Y)은 모두 현재X의 팀이니 X의 팀으로 표시해 준 후 Y를 큐에 집어넣는다. 물론 Y부터는 친구들을 볼거다. Y의 원수는 건너뛴다.

이런식으로 풀었는데 처음에 한 번 틀렸다. 틀린 이유는 처음에 문제에 나온대로 친구의 친구까지만 같은 팀으로 표시했기 때문이다.
문제를 계속 보다가 결국 이해 했고 친구의 친구의 친구의 친구의....~~ 모두 X의 팀이라고 이해했고 고치니까 맞았다.

코드를 참고하자.