[ 백준 1765 ] 닭싸움 팀 정하기 (C++)

백준의 닭싸움 팀 정하기(1765) 문제이다.

[ 문제 바로가기 ]

[ 문제풀이 ]

1) 먼저 문제를 정확하게 이해해보고 어떻게 구현해야할지 천천히 해결해 나가보도록 하자.

   문제에서 닭 싸움의 팀을 정할 때, 조건 2가지를 명시해 놓았다.

   1. 내 친구의 친구는 내 친구이다.

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

   => 나는 친구랑만 같은 팀에 속할 수 있다.

   간단하게 정리해보자면 위와 같다. 사실 본인은 문제를 구현했는데 틀렸습니다 를 굉장히 많이 받았다.

   어디가 문제인지 잘 찾아보다보니, 문제의 조건을 제대로 이해를 하지 못했었다.

   위의 조건에 숨어있는 경우를 한번 설명해보겠다.

   사람이 A B C D 4명이 있다고 가정해보자.

   이 때, A와 B는 친구이고, B와 C는 원수이고, C와 D도 원수라고 생각해보자. 그림으로 표현하자면 다음과 같다.

  

    위와 같은 경우이다. 이 때, A와 D는 팀이 될 수 있을까??

    쉽게 생각해보면 A의 친구인 B와 C가 원수이고, C와 D가 원수니까 2번조건인 '내 원수의 원수도 내 친구이다.' 라고 했으

    므로 같은 팀으로 판단하고 팀이 될 수 있다고 생각할 수 있다. 하지만 ! 2번 조건을 다시 한번 읽어보자.

    "내 원수의 원수도 내 친구이다." 그렇다면, 다시 한번 생각해보자. A와 C는 친구관계일까 원수관계일까 ??

    당연히 원수관계이다. 라고 말을 하면 틀린 것이다. 정확하게 말하자면, A와 C는 친구도 원수도 아닌 관계이다.

    즉, 친구가 아니기 때문에 같은 팀이 될 수 없을 뿐이지 절대로 둘이 원수라고 말할 수는 없다. 왜 ??

    C는 B와 원수이다. A와 원수가 아니다. A의 친구인 B와 원수일 뿐이지, 정확하게 말하자면 A와 C는 원수가 아니다.

    무슨 소린지 이해가 안되겠으면 쉽게 생각을 해보자. 철희 영희 민호 3명이 있다. 여기서 철희와 영희는 친구이다.

    그런데 영희와 민호는 서로 원수지간이다. 그럼 철희와 민호는 원수지간일까??? 아니다. 아무 관계도 아닐 뿐이다.

    단지, 친구가 아니기 때문에 같은 팀이 될 수는 없다. 하지만 원수 관계는 아니라는 것이다 !

    즉, 다시 문제로 돌아와서 A와 D가 같은 팀이 될 수 있는지 생각해보자. 같은 팀이 될 수는 없다. 왜 ?

    "아무 관계도 아니기 때문에" ! A와 D는 친구도 원수도 아니기 때문이다.

     이 쯤에서 2번 조건을 다시 한번 읽어보자. "내 원수의 원수도 내 친구이다."

    누군가는 당연한 이야기를 왜 하고 있지 라고 생각하실 수 있지만, 본인은 이 부분 때문에 굉장히 많은 좌절을 겪었습니다..

2) 그럼 이제 본격적으로 팀을 나누는 부분을 구현해보자.

   본인이 접근한 방식은 DFS를 통한 완전탐색이다. 뭘 탐색했을까?? 1번부터 N번까지 모든 번호를 탐색하면서

   팀이 가능한 사람끼리 묶어주었다.

   가능한 사람이 누군데 ? 현재 탐색하는 번호의 친구 이거나, 현재 탐색하는 번호의 원수의 원수들이다.

   이 부분을 재귀호출을 통해서 최대 깊이까지 들어간 후에 팀으로 만들어 주는 방식으로 구현해 보았다.

   사실, 구현 자체 보다는 문제를 잘 이해하고 어떻게 접근하는지가 더 중요했던 문제였던 것 같다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<queue>
 
#define endl "\n"
#define MAX 1000 + 1
using namespace std;
 
int N, M, Team_Num = 1;
int Already_In_Team[MAX];
vector<int> Enemy[MAX], Friend[MAX];
 
void Input()
{
    cin >> N >> M;
    for (int i = 0; i < M; i++)
    {
        char c;
        int a, b;
        cin >> c >> a >> b;
 
        if (c == 'E')
        {
            Enemy[a].push_back(b);
            Enemy[b].push_back(a);
        }
        else
        {
            Friend[a].push_back(b);
            Friend[b].push_back(a);
        }
    }
}
 
void DFS(int Cur)
{
    Already_In_Team[Cur] = true;
    for (int i = 0; i < Friend[Cur].size(); i++)
    {
        int Next = Friend[Cur][i];
        if (Already_In_Team[Next] == false)
        {
            DFS(Next);
        }
    }
    for (int i = 0; i < Enemy[Cur].size(); i++)
    {
        int Next = Enemy[Cur][i];
        for (int j = 0; j < Enemy[Next].size(); j++)    // Enemy's Enemy is Friend with Cur ! 
        {
            int nNext = Enemy[Next][j];
            if (Already_In_Team[nNext] == false)
            {
                DFS(nNext);
            }
        }
    }
}
 
void Solution()
{
    int Answer = 0;
    for (int i = 1; i <= N; i++)
    {
        if (Already_In_Team[i] == false)
        {
            DFS(i);
            Answer++;
        }
    }
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}