Algospot EDITORWARS

문제 링크입니다: https://algospot.com/judge/problem/read/EDITORWARS

상호 배타적 집합(Union FInd)을 이용하여 푸는 문제였습니다.

알고리즘은 아래와 같습니다.

1. 전형적인 Union Find 자료구조처럼 해당 노드의 루트를 찾는 find 함수와 집합들을 합치는 merge 함수를 정의해줍니다.

2. 두 노드 사이가 적인지 판별하는 dis 함수와 아군인지 판별하는 ack 함수를 정의하는데 모순 발생 시 false를 반환하도록 반환형을 boolean으로 선언합니다.

i) dis 함수에서 같은 집합에 속해 있으면 false를 반환하고, 적의 적은 아군이기 때문에 u와 enemy[v]를 합치고 v와 enemy[u]를 합친 뒤 서로를 적이라고 표시해줍니다.

ii) ack 함수에서도 비슷한 맥락으로 서로가 적대 관계라면 false를 반환하고, 아군의 적은 나의 적이므로 u와 v를 합치고 enemy[u]와 enemy[v]를 합친 뒤 서로를 적이라고 표시해줍니다.

3. 설명들을 입력할 때 2번에서 false를 반환하는 설명이 있다면 해당 설명의 인덱스를 표시하고 숫자들을 다 입력받은 뒤 해당 인덱스와 함께 모순이라고 출력해줍니다.

4. 모순인 설명이 없을 경우 한 파티에 올 가능성이 있는 최대 인원을 구해줍니다.

i) 같은 모임 쌍을 두 번 세지 않기 위해, enemy < node인 경우만 세줍니다.

ii) 적이 없는 노드들도 한번씩 세줍니다.

iii) 아군과 적군 중 규모가 큰 쪽을 출력해줍니다.

#include <iostream>

#include <vector>

#include <string>

#include <algorithm>

using namespace std;

 

int N, M;

 

struct BipartiteUnionFind

{

        //parent[i] = i의 부모 노드, 루트라면 i

        //rank[i] = i가 루트인 경우, i를 루트로 하는 트리의 랭크

        //enemy[i] = i가 루트인 경우, 해당 집합과 적대 관계인 집합의 루트의 번호 (없으면 -1)

        //size[i] = i가 루트인 경우, 해당 집합의 크기

        vector<int> parent, rank, enemy, size;

        BipartiteUnionFind(int n) :parent(n), rank(n, 0), enemy(n, -1), size(n, 1)

        {

                 for (int i = 0; i < n; i++)

                         parent[i] = i;

        }

        int find(int u)

        {

                 if (parent[u] == u)

                         return u;

                 return parent[u] = find(parent[u]);

        }

        int merge(int u, int v)

        {

                 //u나 v가 공집합인 경우 나머지 하나를 반환

                 if (u == -1 || v == -1)

                         return max(u, v);

                 u = find(u);

                 v = find(v);

                 //이미 둘이 같은 트리에 속한 경우

                 if (u == v)

                         return u;

                 if (rank[u] > rank[v])

                         swap(u, v);

                 //이제 항상 rank[v]가 더 크므로 u를 v의 자식으로 넣는다

                 if (rank[u] == rank[v])

                         rank[v]++;

                 parent[u] = v;

                 size[v] += size[u];

                 return v;

        }

        //u와 v가 서로 적이다. 모순이 일어났다면 false, 아니면 true

        bool dis(int u, int v)

        {

                 //우선 루트를 찾는다

                 u = find(u);

                 v = find(v);

                 //같은 집합에 속해 있으면 모순

                 if (u == v)

                         return false;

                 //적의 적은 나의 동지

                 int a = merge(u, enemy[v]);

                 int b = merge(v, enemy[u]);

                 enemy[a] = b;

                 enemy[b] = a;

                 return true;

        }

        //u와 v가 서로 동지다. 모순이 일어났다면 false, 아니면 true

        bool ack(int u, int v)

        {

                 //우선 루트를 찾는다

                 u = find(u);

                 v = find(v);

                 //두 집합이 서로 적대 관계라면 모순

                 if (enemy[u] == v)

                         return false;

                 //동지의 적은 나의 적

                 int a = merge(u, v);

                 int b = merge(enemy[u], enemy[v]);

                 enemy[a] = b;

                 //두 집합 다 적대하는 집합이 없으면 b는 -1일 수 있다

                 if (b != -1)

                         enemy[b] = a;

                 return true;

        }

};

 

//BipartiteUnionFind 인스턴스가 주어질 때

//한 파티에 올 가능성이 있는 최대 인원을 구한다

int maxParty(const BipartiteUnionFind &buf)

{

        int result = 0;

        for(int node=0; node < N; node++)

                 if (buf.parent[node] == node) //루트인 경우만

                 {

                         int enemy = buf.enemy[node];

                         //같은 모임 쌍을 두번 세지 않기 위해, enemy < node인 경우만 센다

                         //enemy==-1인 경우도 정확히 한 번씩 세게 된다

                         if (enemy > node)

                                 continue;

                         int mySize = buf.size[node];

                         int enemySize = (enemy == -1 ? 0 : buf.size[enemy]);

                         //두 집합 중 큰 집합을 더한다

                         result += max(mySize, enemySize);

                 }

        return result;

}

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0); //실행속도 향상

        int test_case;

        cin >> test_case;

 

        for (int t = 0; t < test_case; t++)

        {

                 cin >> N >> M;

 

                 BipartiteUnionFind buf(N);

 

                 bool contradict = false; //모순

                 int num = -1;

 

                 for (int i = 0; i < M; i++)

                 {

                         string s;

                         int node1, node2;

 

                         cin >> s >> node1 >> node2;

                         if (contradict)

                                 continue;

 

                         if (s == "ACK")

                         {

                                 if (!buf.ack(node1, node2)) //모순 발생할 경우

                                 {

                                          contradict = true;

                                          num = i + 1;

                                 }

                         }

                         else

                         {

                                 if (!buf.dis(node1, node2)) //모순 발생할 경우

                                 {

                                          contradict = true;

                                          num = i + 1;

                                 }

                         }

                 }

 

                 if (contradict)

                         cout << "CONTRADICTION AT " << num << "\n";

                 else

                         cout << "MAX PARTY SIZE IS " << maxParty(buf) << "\n";

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

참고: [프로그래밍 대회에서 배우는 알고리즘 문제해결전략]