[ SWEA 7988 ] 내전 경기 (C++)

SWExpertAcademy의 내전 경기(7988 / D4) 문제이다.

[ 문제풀이 ]

팀원들 간의 시너지 발생 가능한 조합이 주어질 때, 시너지를 발생시키지 않고 2개의 팀을 만드는 것이 가능한지

구해야 하는 문제이다.

가장 먼저, 입력이 문자열 형태로 주어지다 보니, 문자열을 관리하는 로직이 하나 필요하다.

A라는 문자열과 B라는 문자열은 서로 시너지가 발생하는 조합이다 라는 것을 단순하게 int형 숫자로 0번 사람과 1번 사람은 시너지가 발생하는 조합이다 라고 표현한다면 접근하기 쉬울 거라 생각했다.

본인은 STL에서 제공하는 'map'이라는 자료구조를 사용하였다.

map이 엄청나게 자주 쓰이지는 않으니 이번 문제에서 사용한 map의 함수들에 대해서만 간단하게 몇 가지만 알아보고 가보자.

먼저 map은 key와 value 값을 쌍으로 관리할 수 있는 자료구조이다.

이 문제에서 본인은 key값은 string 형으로, value 값은 int 형으로 선언해주었다.

map<string, int> MAP;

key값을 string형으로 선언해준 이유는 입력으로 주어지는 문자열을 key값으로 관리하기 위해서이고

해당 문자열의 value값을 해당 문자열을 나타내는 '정수'로 표현하기 위해서 value 값을 int형으로 선언해 주었다.

map에서는 'count()'라는 함수가 존재한다.

count(key값) 은 해당 key값을 가진 원소들의 갯수를 반환해주는 함수인데 본인은 이 함수를 이용했다.

예를 들어서 입력으로 "A B", "B C" 가 주어졌다고 가정해보자.

그럼 가장 초기에 map에는 아무런 값도 없기 때문에 map.count(A)의 값은 0일 것이다.

왜냐하면 문자열 "A"라는 key값을 가진 원소의 갯수는 0개이기 때문이다.

그럼 이 때, map에 <A , 0> 이라는 값을 넣어주는 것이다.

이후, map.count(B)의 값의 값을 확인해봐도 0일 것이다.

왜냐하면, 문자열 "B"라는 key값을 가진 원소의 갯수는 0개이기 때문이다.

지금까지 map에 넣은 원소는 <A , 0> 밖에 존재하지 않는다.

그럼 이 떄, map에 <B , 1> 이라는 값을 넣어주는 것이다.

왜 A는 0을 함께 넣어주고, B는 1을 함께 넣어줬을까? 위에서도 말했듯이 바로 문자열을 하나의 정수처럼 표현하기 위함이다.

이 후, " B C"라는 입력에서 B가 들어올 때를 봐보자.

map.count(B)를 했더니 1이 반환되었다. 왜 ?? "B"라는 key값을 가진 원소의 갯수는 이미 1개가 존재하기 때문이다.

그럼 이 말은 즉, "이미 문자열 "B"는 고유의 값을 가지고 있습니다." 라고 판단할 수 있는 것이다.

이 경우에는 map에 새로운 원소를 추가해주지 않는다.

마지막으로 map.count(C)를 했더니 0이 반환될 것이고, <C , 2>를 넣어주는 것이다.

코드로 본다면 다음과 같이 구현이 가능하다.

for (int i = 0; i < K; i++)
{
    string A, B; 
    cin >> A >> B;
    if (MAP.count(A) == 0) MAP[A] = Idx++;
    if (MAP.count(B) == 0) MAP[B] = Idx++;
    V[MAP[A]].push_back(MAP[B]);
    V[MAP[B]].push_back(MAP[A]);
}

line 5 ~ 6의 조건문을 보게되면, 해당 문자열이 MAP에 존재하는지 안하는지를 파악한다.

존재한다면 0이 아닌 값이 반환될 것이고, 존재하지 않는 처음 나온 문자열이라면 0이 반환될 것이다.

우리는 "처음 나온 문자열일 때"를 처리해 주면 된다. 어떻게 ? 고유의 값을 넣어주면서 MAP에 넣어주는 것이다.

MAP에 삽입하는 방법으로는 insert()함수를 이용하는 방법도 있지만 위의 본인이 한 것과 같이 MAP[A] = Idx 이런식으로

삽입을 할 수도 있다. MAP[A] = Idx 라는 것은 MAP에 <A (string), Idx(int)> 를 삽입한다는 것과 같은 의미이다.

이런 방법으로 문자열을 마치 정수화 시킨 것 처럼 관리해 주었고, line 8 ~ 9 에서 보게 되면, 'V'가 본인이 위에 선언해 놓은

vector를 의미하는데, 정수화 된 문자열들을 서로 시너지가 존재하는 관계라고 표시하기 위해서 vector에 저장해 주었다.

그럼 이제 시너지가 발생 안하는 팀을 만들 수 있는지 알아보자.

이 부분은 이분 그래프를 이용해서 접근해보았다. 이분그래프도 따로 포스팅해놓은 내용이 없기 때문에 간략하게만

알아보고 가자.

이분 그래프 라는 것은, "그래프에서 인접한 정점끼리는 무조건 다른색으로 칠했을 때, 모든 정점을 두 가지 색으로만

칠할 수 있는 그래프" 를 의미한다.

예를 들면 다음과 같은 그래프는 이분 그래프라고 할 수 있다.

왜 위의 그래프는 이분 그래프가 되는지 알아보자.

가장 간단하게 색깔을 칠해보면 된다. 대신 "인접한 정점끼리는 무조건 다른색으로 칠할 수 있어야 한다."

가장 먼저 위의 그림처럼 하나의 정점을 파랑색으로 칠했다고 가정해보자. 그럼 인접한 정점을 다른색으로 칠해야 하니

빨간색으로 칠해보자.

빨강색으로 칠했으니 또 해당 정점에서 인접한 정점을 다른색으로 칠해보자. 하지만 ! 색깔은 오로지 2개만 사용할 수 있다.

그럼 빨강색으로 칠했으니 반드시 다른색으로 칠해야 하고, 색깔은 이미 '파랑', '빨강' 2가지 색깔이 다 나왔으니

파랑색으로 칠하는 경우밖에 남아있지 않다. 그럼 파랑색으로 칠해보자.

위의 그래프를 보면 "인접한 정점은 서로 다른 색깔을 가져야 한다" 라는 조건을 만족하면서도 동시에

"모든 정점을 단 2가지 색깔로만 칠할 수 있다"라는 조건 까지 만족한다. 따라서 위의 그래프는 이분 그래프이다.

옆에 있는 그림도 표현해보자면 다음과 같이 표현이 가능하다.

이렇게 하면 "인접한 정점끼리는 모두 다른 색깔을 가지면서, 모든 정점을 2가지 색깔로만 채울 수 있기 때문"에

이분그래프이다.

반대로 아래의 그래프는 이분 그래프가 아니다.

왜 그런지 색깔을 한번 칠해보자.

아까와 동일하게 첫번째 정점을 파랑색으로 칠했고, 이어서 인접한 정점을 빨강색으로 칠해보자.

이어서 빨강색과 인접한 정점들 중, 색깔을 아직 칠하지 않은 정점들을 모두 파랑색으로 칠해보자.

이렇게 되면 모든 정점들에 색깔을 칠하게 되었는데 색깔을 보면 파랑색과 빨강색 2가지 색깔만 사용하긴 했는데,

아래 2개의 정점을 보게 되면, 서로 인접한 정점임에도 같은 색깔로 칠해져있다.

즉, 위의 그래프는 이분 그래프의 조건을 위반하므로 이분 그래프가 아니다.

이분 그래프가 위와 같은 그래프이다. 다시 본론으로 돌아와보자.

이분 그래프를 설명한 이유부터 다시 알아보자면, 시너지를 가진 조합을 팀으로 만들면 안되기 때문에 라는 맥락을

서로 다른 색깔로 칠해야 한다 라고 보면 된다. 그러면서 모든 정점을 2가지 색깔로만 채워야한다 라는 맥락을

2팀으로 만들 수 있냐 라고 보면 된다.

즉, 주어진 정점들을 인접한 정점들 끼리는 서로 다른 색깔을 가지도록 모든 정점을 다 칠할때 까지 반복 후,

최종적으로 인접한 정점들 중에서 같은 색깔을 가진 정점들이 존재하는지 파악해주면 된다.

이분 그래프에 대한 코드적인 설명은 소스코드에 주석으로도 충분히 이해할 수 있을 것이다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<map>
#include<string>
 
#define endl "\n"
#define MAX 210
using namespace std;
 
int K, Idx;
map<string, int> MAP;
vector<int> V[MAX];
int Visit[MAX];
string Answer;
 
void Initialize()
{
    Idx = 0;
    MAP.clear();
    for (int i = 0; i < MAX; i++)
    {
        V[i].clear();
        Visit[i] = 0;
    }
}
 
void Input()
{
    cin >> K;
    for (int i = 0; i < K; i++)
    {
        string A, B; 
        cin >> A >> B;
        if (MAP.count(A) == 0) MAP[A] = Idx++;
        if (MAP.count(B) == 0) MAP[B] = Idx++;
        V[MAP[A]].push_back(MAP[B]);
        V[MAP[B]].push_back(MAP[A]);
    }
}
 
void DFS(int Cur, int Color)
{
    Visit[Cur] = Color;
    /* 서로 인접한 정점들을 나와는 다른 색깔로 칠해주어야 한다. */
    /* 색깔을 가장 단순하게 1과 2로 생각해보면 */
    /* 내가 현재 1이라면, 내 인접한 정점들은 2가 되어야 하고 */
    /* 내가 현재 2라면, 내 인접한 정점들은 1이 되어야 한다. */
    /* 즉, 현재 내가 x 라는 색깔이라면, 내 인접한 정점들은 3 - x 가 되어야 한다. */
    /* x = 1 이라면 3 - x = 2 */
    /* x = 2 라면, 3 - x = 1 */
    for (int i = 0; i < V[Cur].size(); i++)
    {
        int Next = V[Cur][i];
        if (Visit[Next] == 0) DFS(Next, 3 - Color);
    }
}
 
void Solution()
{
    for (int i = 0; i < Idx; i++)
    {
        /* Visit배열은 int형 배열로써 3가지 상태를 나타낸다. */
        /* 1. 아직 색깔을 칠하지 않음. */
        /* 2. 파랑색으로 칠했음. */
        /* 3. 빨강색으로 칠했음. */
        /* 최소 3개의 상태를 표현해야 하므로, 단순 bool 형으로는 계산 불가.*/
        if (Visit[i] == 0)    // 색깔을 칠하지 않은 정점에 대해서 DFS탐색.
        {
            DFS(i, 1);
        }
    }
 
    /* 모든 정점을 칠해봤으면 이제 인접한 정점들 중에 같은 색깔을 가진 정점들이 있는지 확인. */
    for (int i = 0; i < Idx; i++)
    {
        int Cur = i;
        for (int j = 0; j < V[i].size(); j++)
        {
            int Next = V[i][j];
            if (Visit[Cur] == Visit[Next])
            {
                Answer = "No";
                return;
            }
        }
    }
    Answer = "Yes";
}
 
void Solve()
{
    int Tc; cin >> Tc;
    for (int T = 1; T <= Tc; T++)
    {
        Initialize();
        Input();
        Solution();
 
        cout << "#" << T << " " << Answer << endl;
    }
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}