[백준] 23818 원수의 원수 (C++)

링크: https://www.acmicpc.net/problem/23818

23818번: 원수의 원수

문제

원수의 원수는 친구라는 속담이 있다! 이 속담과 함께라면 어떤 두 사람이든 그 쌍의 관계를 알 수 있다. A와 C라는 사람이 직접적으로 관계가 없더라도, A와 B가 관계가 있고 B와 C가 관계가 있다면 A와 C라는 사람도 간접적으로 관계가 있다. 이를 정리하면 아래와 같다.

1. A와 B가 원수 관계이고 B와 C가 원수 관계이면 A와 C는 친구 관계이다.
2. A와 B가 원수 관계이고 B와 C가 친구 관계이면 A와 C는 원수 관계이다.
3. A와 B가 친구 관계이고 B와 C가 친구 관계이면 A와 C는 친구 관계이다.

이를 바탕으로 사람들 간의 관계가 주어질 때, 특정 사람 간의 관계가 무엇인지를 확인해보자!

입력

사람의 수 N(2 ≤ N ≤ 100,000)과 관계의 수 M(0 ≤ M ≤ 100,000) 그리고 대답해야 할 관계의 수 K(1 ≤ K ≤ 100,000)가 입력으로 들어온다.

그 후 M개의 줄에 걸쳐 t∈{0,1}, a, b (1≤ a, b ≤ N, a ≠ b) 가 입력으로 들어오게 된다.

t = 0일 경우 a, b가 친구 관계임을 의미한다.

t = 1일 경우 a, b가 원수 관계임을 의미한다.

그 후 K개의 줄에 걸쳐 쿼리 a, b (1≤ a, b≤ N,a ≠b)가 입력으로 들어오게 된다.

출력

각 쿼리에 대해 a와 b의 관계를 각 줄마다 출력하면 된다.

a와 b가 전혀 관련이 없을 경우 'Unknown'을 출력한다.

 a와 b가 친구 관계인 경우 'Friend'를 출력한다.

 a와 b가 원수 관계인 경우 'Enemy'를 출력한다.

 a와 b가 친구 관계이자 원수 관계인 경우 'Error'를 출력한다.

 

---

풀이

 

처음 문제를 보았을 때는 매우 쉬워보였으나 그렇지 않은 문제이다.

사람의 수가 최대 100,000명이기 때문에 사람들의 관계를 100,000 × 100,000 의 배열에 저장하는 것도 불가능하였고

관계를 벡터로 저장한 뒤 DFS로 접근하려고 해도 문제가 많이 발생하였다.

 

먼저 위 문제를 푸는 데 중요한 핵심 아이디어는 관계의 합이다.

예를 들어 A와 B의 관계가 1, B와 C의 관계가 1일 때 A와 C의 관계는 (1+1) mod 2 = 0, 친구이다.

더 나아가 C와 D의 관계가 1일 때 A와 D의 관계는 (1+1+1) mod 2 = 1, 원수이다.

 

위 아이디어를 바탕으로 사람들의 관계를 Union-Find로 정리하면 위 문제를 간단히 풀 수 있다.

한 사람당 여러 명과 관계가 있을 수 있으므로 Union-Find로 푸는 문제가 아닐 줄 알았는데 그렇지 않았다.

root 배열에 {관계를 맺은 사람, 관계}를 저장해나가며 1번 예제를 푸는 과정은 다음과 같다.

 

먼저 기본적으로 각 노드는 자기 자신과 친구 관계이므로 위와 같이 기본값은 저장한다.

 

입력으로 1 1 2가 들어오면 2번 노드를 {1, 1}로 업데이트한다.

 

입력으로 1 2 3이 들어오면 3번 노드를 {2, 1}로 업데이트한다.

 

입력으로 0 3 4가 들어오면 4번 노드를 {3, 0}으로 업데이트한다.

 

입력으로 0 4 5가 들어오면 5번 노드를 {4, 0}으로 업데이트한다.

 

이어서 1과 3의 관계를 묻는다면 (1+1) mod 2 = 0, 친구이다.

 

마찬가지로 1과 5의 관계를 묻는다면 (1+1+0+0) mod 2 = 0, 친구이다.

 

하지만 위의 예제와는 다르게 한 사람은 여러 명과 관계를 갖고 있을 수 있다.

2번 예제를 푸는 과정은 다음과 같다.

 

입력으로 1 1 2가 들어오면 2번 노드를 {1, 1}로 업데이트한다.

 

입력으로 0 2 3이 들어오면 3번 노드를 {2, 0}으로 업데이트한다.

 

입력으로 0 1 3이 들어오면 문제가 발생한다.

그동안은 입력으로 들어온 두 사람의 부모가 달랐기 때문에 문제 없이 Union 연산을 수행할 수 있었지만,

1번 사람의 부모가 1, 3번 사람의 부모도 1로 두 사람의 부모가 같기 때문에 문제가 발생한다.

 

이 때는 기존에 저장된 관계와 새롭게 입력으로 들어온 관계를 비교하여

두 관계가 일치한다면 별다른 업데이트 없이 계속 진행하면 되고

두 관계가 일치하지 않는다면 모순이 발생하므로 Error가 발생했음을 알 수 있다.

위 예시에서도 기존 1과 3의 관계는 1이지만 주어진 관계가 0으로 두 관계가 달라 Error가 발생하였다.

 

또한 중요한 점이 하나 더 있는데, 한 번이라도 Error가 발생한 그래프(관계)는 모든 노드의 관계가 Error가 된다는 것이다.

따라서 위의 1, 2, 3번 사람과 연결되는 다른 사람들이 있다면 그 관계는 무조건 Error이다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
using namespace std;

int n, m, k;
pair<int, int> root[100001];
bool error[100001];

void resetRoot(){
    for (int i = 1; i <= n; i++){
        root[i] = {i,0};
    }
}

// {관계의 대상이 되는 사람, 관계} 를 저장
pair<int, int> Find(int a, int r){
    if (a == root[a].first){
        return {a, r};
    }
    else{
        return Find(root[a].first, (r+root[a].second)%2);
    }
}

void Union(int a, int b, int r){
    pair<int, int> parentA = Find(a, 0);
    pair<int, int> parentB = Find(b, 0);
    // a와 b의 부모가 같은 경우
    if (parentA.first == parentB.first){
        // 기존의 관계와 주어진 관계가 다른 경우 Error
        if ((parentA.second+parentB.second)%2 != r){
            error[parentA.first] = true;
        } 
    }
    // a와 b의 부모가 다른 경우
    else{
        if (parentA.first < parentB.first){
            root[parentB.first] = {parentA.first, (r + parentA.second + parentB.second)%2};
            // parentB.first가 Error인 경우 parentA.first도 에러
            if (error[parentB.first]){
                error[parentA.first] = true;
            }
        }
        else{
            root[parentA.first] = {parentB.first, (r + parentA.second + parentB.second)%2};
            // parentA.first가 Error인 경우 parentB.first도 에러
            if (error[parentA.first]){
                error[parentB.first] = true;
            }
        }
    }
}



int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    cin >> n >> m >> k;
    resetRoot();

    for (int i = 0; i < m; i++){
        int t, a, b;
        cin >> t >> a >> b;
        
        Union(a, b, t);
    }


    while (k--){
        int a, b;
        cin >> a >> b;

        pair<int, int> parentA = Find(a, 0);
        pair<int, int> parentB = Find(b, 0);

        // 부모가 다른 경우 Unknown
        if (parentA.first != parentB.first){
            cout << "Unknown\n";
        }
        // 부모가 같은 경우
        else {
            // 부모가 에러인 경우
            if (error[parentA.first]){
                cout << "Error\n";
            }
            // 이외의 경우 관계를 계산
            else{
                int relation = (parentA.second + parentB.second)%2;
                if (relation){
                    cout << "Enemy\n";
                }
                else{
                    cout << "Friend\n";
                }
            }
        }

    }
}