[알고스팟] EDITORWARS - 에디터 전쟁 (C++, 분리 집합)

문제

 

https://algospot.com/judge/problem/read/EDITORWARS

algospot.com :: EDITORWARS

 

 

풀이

 

종만북 난이도: 중

 

분리 집합(Disjoint Set, 종만북에서는 상호 배타적 집합으로 해석되어 있다.) 문제는 처음이라 상당히 애먹었다.

분리 집합 문제들에서 사용하는 자료구조인 유니온-파인드(Union-Find)를 적절히 수정해서 풀어야 하는 문제이다.

 

파티에 올 수 있는 사람수를 구하기 위해 집합의 크기를 저장하는 것은 set_size 배열에 집합의 루트가 집합의 크기를 저장하게 하면 간단히 구현할 수 있다.

 

이에 따른 Union(두 노드가 속한 트리를 합치기)과 Find(노드가 속한 트리의 루트를 찾음) 함수는 아래와 같다.

 

int Find(int u){  //u가 속한 트리의 루트 찾기
  if(parent[u] == u)
    return u;
  return parent[u] = Find(parent[u]);
}
 
int Union(int u, int 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]) //항상 v의 rank가 더 크거나 같게
    swap(u, v); 
 
  parent[u] = v;
  set_size[v] += set_size[u];
  if(rank[u] == rank[v]) //같은 경우만 v의 rank가 1 증가
    ++rank[v];
 
  return v;
}

Find() 함수 호출 시, 항상 모든 노드가 자신의 부모로 해당 트리의 root노드를 가리키게 만들면 빠르게 해당 노드가 속한 트리의 루트를 알 수 있다. 이를 경로 압축(path compression)이라고 한다.

 

rank[root]는 root의 트리 높이를 의미한다.

rank를 활용하여 두 트리를 Union 할 때 항상 rank가 더 큰 트리의 하위로 합쳐주면 트리가 한쪽으로 편향되는 것을 막을 수 있다.

이는 Find 함수가 재귀 호출을 통해 한 단계씩 상위 노드로 접근하기 때문에 트리의 높이가 길어질수록 시간이 오래 걸리기 때문에 중요하다.

 

이제 각각의 댓글의 정보를 통해 a가 속한 트리와 b가 속한 트리를 Union 시키거나 서로 배척해야한다.

처음에는 각 트리의 root가 배척해야 하는 모든 트리의 root를 저장시키려 했지만

사실 배척하는 트리의 root는 한 개씩만 저장해도 충분하다.

그 이유는 아래의 Ack함수와 Dis 함수의 구현을 먼저 본 다음 설명하겠다.

 

 

bool Ack(int u, int v){
  u = Find(u);
  v = Find(v);
 
  if(enemy[u] == v) //서로의 집합이 적인 경우 모순
    return false;
  
  int a = Union(u, v), b = Union(enemy[u],enemy[v]);// 우리의 적들은 서로 동지
  enemy[a] = b;
  if(b != -1) enemy[b] = a;
  return true;
}
 
bool Dis(int u, int v){
  u = Find(u);
  v = Find(v);
 
  if(u == v)  //같은 집합에 있는 경우 모순
    return false;
 
  int a = Union(u, enemy[v]), b = Union(v, enemy[u]);
  enemy[a] = b;
  enemy[b] = a;
  return true;
}

 

enemy[root]에는 root의 트리(집합)가 배척하는(자신의 집합과는 반대의 에디터를 옹호하는 집합) 트리의 루트가 저장되어있다.

(초기에는 어떤 정보도 입력되지 않았으므로 enemy[]에  -1을 저장해 두자.)

 

 

bool Ack(int u, int v)

Ack함수는 u와 v가 같은 집합에 속할 수 있다면 서로가 속한 트리를 합치고 true를 반환한다.

만약 서로가 같은 집합에 속할 수 없다면, 서로의 집합이 적인 경우이다.

이 경우 false를 반환해주자.

 

같은 집합에 속할 수 있다면, u와 v를 Union하여 서로의 집합을 합해준다. 합한 집합의 루트를 a라고 하자.

이때 u와 v는 동지 집합이 되므로 u와 v의 적 집합들은 서로 동지일 것이다.

따라서 enemy[u]와 enemy[v]도 Union 해준다. 적들이 합해진 집합의 루트는 b라고 하자.

 

이제 a와 b는 서로 배척 관계이므로 서로를 enemy[]로 저장해준다.

 

그림으로 관계를  표현해 보면 다음과 같다.

 

 

 

u와 v의 집합이 동지(결합하면 a집합)가 되면서 두 개의 적 집합 enemy[u]와 enemy[v]이 생기지만

결국 적 집합끼리도 Union을 시키기 때문에 최종적으로 a의 집합의 적은 집합 b 한 개뿐이다.

따라서 적을 저장하는 enemy는 상대 집합의 루트 하나만 저장해도 충분하다.

 

만약 적들의 집합이 서로 배척한다면 어떡해야 할지 생각할 수도 있지만 enemy는 한 개의 적 루트만을 저장하기 때문에 u와 v의 적 집합으로 선택되었다면 서로를 배척할 수는 없다.

 

bool Dis(intu,intv)도 동일한 방식으로 구현해주자.

 

이제 문제는 댓글들에 모순이 없는 경우 구해야 하는 파티 멤버의 최댓값이다.

간단히 생각하면 만들어진 집합 중에 가장 크기가 큰 값이 답이라고 생각할 수가 있지만 아니다.

여러 개의 집합 중에 서로 배척하지 않는(적 관계가 아닌) 집합이라면 같은 에디터를 옹호할 수 도 있다.

따라서 적 관계인 두 집합 중에서는 더 큰 크기의 집합을 파티 멤버로 포함하여 최대 파티 멤버를 구성하자.

 

또한 한 번도 댓글을 달지 않는 멤버가 어떤 집합에 포함될지 알 수가 없다. 이들은 모두 파티 멤버가 될 가능 성이 있으므로 모두 포함시켜주자.

 

이를 구현한 int FindMaxParty()함수는 최대 파티 멤버를 반환한다.

 

int FindMaxParty(){
  int max_party_size =0;
  for(int idx=0; idx<set_size.size() ; ++idx){
    if(parent[idx] == idx){
      int enemy_idx = enemy[idx];
 
      if(enemy_idx > idx)
        continue;
        
      int my_size = set_size[idx];
      int enemy_size = enemy_idx == -1 ? 0 : set_size[enemy_idx];
      max_party_size += max(my_size, enemy_size);
    }
  }
  return max_party_size;
}

 

이때 enemy_idx< idx 인 경우만 계산을 진행하는 이유는

모든 노드를 차례로 순회하다 보면 서로 적 관계인 노드는 결국 한 번씩 다 방문된다.

그때마다 두 집합 중 더 큰 집합을 멤버 수에 포함시키면 중복된 계산이 되므로 enemy_idx> idx인 경우는 넘어가 주자.

 

사실상 종만북을 따라 하듯 구현을 했다... 반성하자.

코드