L. Cow Evolution

Editor: 최연웅(yonsweng)

문제 상황 설명

input으로는 각 sub-population에 있는 소가 가진 특성들이 들어옵니다. 예제 데이터를 봅시다.

4
2 spots firebreathing
0
1 flying
2 telepathic flying

sub-population #1은 spots, firebreathing 특성을 가지며, #2는 아무 특성도 가지지 않고, #3은 flying, #4는 telepathing flying 특성을 가집니다.

sub-population #1에 해당하는 노드는 루트로부터 spots, firebreathing 간선을 거쳐서 도착해야 합니다. 다른 sub-population이 spots이나 firebreathing을 포함하고 있지 않으므로 그냥 루트로부터 spots, firebreathing 간선을 그리고 리프 노드에 sub-population #1을 놓으면 됩니다.

sub-population #2는 루트로부터 아무 특성이 없는 간선를 거쳐서 오면 됩니다.

그러나 sub-population #3, 4는 flying 특성을 공통으로 가지고 있기 때문에 루트(혹은 루트로부터 아무 특성이 없는 간선만 거쳐서 온 노드) 아래 flying 간선을 그리고 그 밑에 특성이 없는 간선과 telepathic 간선을 그리고 리프 노드에 각각 sub-population #3, 4를 두면 됩니다.

이렇게 트리를 그리면, 문제에 있는 그림이 나오게 됩니다. 이와 같이 간선이 중복되지 않게 트리를 그릴 수 있으면 이 트리를 proper라고 하고 "yes"를 출력하면 됩니다.

그러면, 트리를 그릴 수 없는 경우를 살펴볼까요?

5
1 spots
2 spots firebreathing
2 flying firebreathing
1 telepathic
2 telepathic spots

이 경우, sub-population #1, 2는 spots 간선을 공통으로 가지고 그 밑에 특성이 없는 간선과 firebreathing 간선을 거쳐서 각각 노드에 도착하면 됩니다. sub-population #3은 firebreathing 간선을 거쳐서 내려와야 하는데, spots 간선을 거치지 않고 그리려면 firebreathing이라는 간선이 두 번 중복해서 그려지게 됩니다. 그래서 이 데이터에 대해서는 proper 트리를 그릴 수 있는 방법이 없습니다.

문제 풀이

이제는 약간 관점을 바꿔서 어떤 특성에 대해 그 특성을 가지고 있는 sub-population을 집합으로 나타내봅시다.

spots = {1, 2, 5}

firebreathing = {2, 3}

flying = {3}

telepathic = {4, 5}

이는 각 특성의 간선을 거쳐야 하는 sub-population의 목록과 같습니다. 즉, sub-population #1, 2, 5는 spots이라는 간선을 거쳐서 도착해야 하는 것입니다. 그렇다면 어떤 특성 A, B가 공통 원소 c를 가지고 있다면, c에 해당하는 노드는 루트로부터 A, B에 해당하는 간선을 거쳐서 도착해야 하기 때문에 A 간선과 B 간선은 같은 경로에 있어야 합니다. 그리고 같은 경로에 두 간선이 있다면, 두 간선을 타고 내려온 sub-population의 집합은 한 간선을 타고 내려온 sub-population의 집합의 부분집합이므로 A가 B의 부분집합이거나, B가 A의 부분집합이어야 합니다. 예시로 설명을 하자면, spots와 firebreathing은 공통 원소 2를 가지고 있기 때문에 spots이 firebreathing의 부분집합이거나, firebreathing이 spots의 부분집합이어야 합니다. 한편, 특성 A, B가 공통 원소를 가지지 않는다면, 문제가 생기지 않습니다.

코드는 단순합니다.

1. 따라서 각 특성에 대해 그 특성을 가지고 있는 sub-population을 리스트에 넣습니다. (K<=25이므로 비트 연산을 이용해 한 int 변수에 넣을 수 있습니다.)

2. 모든 두 특성의 조합에 대해서, 그 두 특성이 서로 부분집합 관계이거나 서로소이면 "yes", 아니면 "no"를 출력하고 끝냅니다.

정답 소스 (C++)

#include <iostream>
#include <map>

using namespace std;

int main() {
    map<string, int> fmap;

    int n;
    cin >> n;
    for(int i=0; i<n; i++) {
        int k;
        cin >> k;
        while(k-- > 0) {
            string feature;
            cin >> feature;
            if(fmap.find(feature) == fmap.end())  // feature not found in fmap.
                fmap[feature] = (1 << i);  // i번째 비트에 1, 나머지는 0으로 초기화.
            else
                fmap[feature] |= (1 << i);  // i번째 비트를 1로 바꾼다.
        }
    }

    bool flag = false;
    for(auto A : fmap) {
        for(auto B : fmap) {
            int a = A.second, b = B.second;
            if((a | b) == a || (a | b) == b)  // 부분집합 관계.
                continue;
            else if((a & b) == 0)  // 서로소.
                continue;
            else {
                flag = true;
                break;
            }
        }
        if(flag) break;
    }

    if(!flag)
        cout << "yes";
    else
        cout << "no";

    return 0;
}