[백준 / BOJ] 1765 닭싸움 팀 정하기 (Java)

문제

출처 : https://www.acmicpc.net/problem/1765

1765번: 닭싸움 팀 정하기

n명의 학생, m개의 학생들 사이의 관계가 주어졌을때, n명의 학생들로 최대 몇개의 팀을 만들수있는지 알아내는 프로그램을 만드는 문제다.

 

---

풀이

문제 해석이 정말 어려운 문제였다.

 

문제에서 인간관계를 다음과 같이 정리할 수 있다고 한다.

1. 내 친구의 친구는 내 친구이다.
2. 내 원수의 원수도 내 친구이다.

처음에 이걸보고 가능한 인간관계 경우의 수를 다음과 같이 생각했다.(재귀적으로)

1. 내 친구의 친구는 내 친구이다.
2. 내 친구의 원수의 원수는 내 친구이다.
3. 내 친구의 원수의 친구는 내 친구가 아니다.
4. 내 원수의 친구는 내 친구가 아니다.
5. 내 원수의 원수의 친구는 내 친구이다.
6. 내 원수의 원수의 원수는 내 원수이다.

위 6가지 경우의 수중 4번은 성립하지 못한다.

이것을 이해하기 위해서는, "원수"라는 단어의 의미를 자세히 생각해볼 필요가 있다.

 

내가 B와 원수일때, B의 친구인 C와 항상 원수인지는 알수없다.

즉, 내가 B와 원수라고 하더라도, B의 친구와는 어떤 사이인지 알수 없다는것이다.

 

또한 이 문제에서 원하는것은 한 팀을 이루는 모든 학생이 친구라는것이다.

따라서, 문제를 풀기위해선, 친구의 친구는 친구이다를 성립시켜야한다.

 

이제, 한 팀이 될수있는 경우의 수를 다시 생각해보면,

1. 내 친구의 친구는 친구이다.
2. 내 원수의 원수는 나와 친구이다.
3. 2번에 의해서, 내 원수의 원수의 친구는 내 친구의 친구가 되어서, 친구이다.

위 조건이 성립하는 경우만 재귀로 들어가서 찾아주면 답이 된다.

 

좀 더 쉽게 풀기 위해서, 다음 한가지 경우의 수만 배제하며 탐색할수도 있다.

 

원수의 친구는 나와 아무런 사이가 아니다. 

- 이것이 성립하는 이유는 다음과 같다.

- 원수의 친구는 나와 아무런 사이가 아니기 때문에, 이 다음부터 나오는 모든 학생들과 나의 관계는 알수없다.

 

주요 소스코드

    private void findFriends(int idx, boolean isFriend, boolean[] dupCheck){
        if(dupCheck[idx]) return;
        dupCheck[idx] = true;
        if(isFriend) check[idx] = true;
        if(isFriend) for(int i = 0; i < arr[idx].friend.size(); i++){
            int nNode = arr[idx].friend.get(i);
            if(dupCheck[nNode]) continue;
            findFriends(nNode, isFriend, dupCheck);
        }
        
        for(int i = 0; i < arr[idx].enemy.size(); i++){
            int nNode = arr[idx].enemy.get(i);
            if(dupCheck[nNode]) continue;
            findFriends(nNode, (isFriend == true) ? false : true, dupCheck);
        }
    }

---

전체 소스코드

https://github.com/devxb/JJUNalgo/blob/master/BOJ%20source%20code/1765%20%EB%8B%AD%EC%8B%B8%EC%9B%80%20%ED%8C%80%20%EC%A0%95%ED%95%98%EA%B8%B0./Main.java

GitHub - devxb/JJUNalgo: 백준 알고리즘 소스코드🙃