0726-tree.md

2020.07.26

📚공부한 거 List📚

• 트리 - 25. 상호 배타적 집합(2)

---

[종만북] 상호 배타적 집합

상호 배타적 집합의 최적화

트리를 사용해서 상호 배타적 집합을 표현할 경우 생기는 문제점

👉 연산의 순서에 따라 자칫 트리가 한쪽으로 기울어질 수 있다.

해결방안 1 :: 랭크(rank)에 의한 합치기(union-by-rank) 최적화

👉 두 트리를 합칠 때, 항상 높이가 더 낮은 트리를 더 높은 트리 밑에 집어넣음으로써 트리의 높이가 높아지는 상황을 방지한다.

-----(2020.07.25 공부내용)-----

랭크에 의한 합치기 최적화를 이용한 상호 배타적 집합의 구현

struct OptimizedDisjointSet {
  //parent[i] : i의 부모
  //rank[] : 해당 노드가 한 트리의 루트일 경우 해당 트리의 높이 저장
  vector<int> parent, rank;
  OptimizedDisjointSet(int n) : parent(n), rank(n,1) {
    for(int i=0; i<n; ++i) parent[i] = i;
  }
  //u가 속한 트리의 루트 번호 반환하는 함수
  int find(int u) {
    if(u == parent[u]) return u;
    return parent[u] = find(parent[u]);
  }
  //u가 속한 트리와 v가 속한 트리를 합치는 함수
  void merge(int u, int v) {
    //u와 v가 속한 트리의 루트를 각각 구한다.
    u = find(u);
    v = find(v);
    //u와 v가 이미 같은 집합에 속하면 합치기 연산 필요 없다.
    if(u==v) return;
    //만약 u가 속한 트리의 높이가 더 높으면, u와 v를 교환한다.
    if(rank[u] > rank[v]) swap(u,v);
    //u의 트리의 높이가 v가 속한 트리의 높이보다 같거나 낮은 상태이다. 
    parent[u] = v; //u의 부모를 v로 설정하므로써, u의 트리를 v의 트리에 합친다.
    //만약 두 트리의 높이가 같다면, 합쳐진 결과 트리 v의 높이는 1 증가한 상태이다.
    if(rank[u] == rank[v]) ++rank[v];
  }
};

⏱Time-Complexity⏱

이렇게 최적화를 하면 find() 연산시간을 줄일 수 있다.

트리의 높이는 **lg(포함한 노드의 수)**에 비례하여 합치기 연산과 찾기 연산의 시간복잡도는 **O(lgN)**이다.

해결방안 2 :: 경로 압축(path compression) 최적화

👉 find(u)를 통해 u가 속하는 트리의 루트를 찾았을 때 parent[u]값을 이 루트로 바꾸면 또 다시 find(u)가 호출되었을 때 바로 루트를 찾을 수 있다.

int find(int u) {
    if(u == parent[u]) return u;
    return parent[u] = find(parent[u]);
  }

📝예제::그래프의 연결성 확인하기

N개의 도시가 도로망으로 연결되어 있고 각 도로가 정확히 두 개의 도시를 연결한다. 폭설로 인한 도로 마비 후 도로가 하나씩 복구될 때마다 임의의 두 도시 간에 서로 왕래가 가능한지 알아보는 문제.

⚡️keypoint⚡️

1. 각 도시를 원소로 하고, 왕래가 가능한 도시들을 하나의 집합으로 표현한다.
2. a,b를 연결하는 도로가 복구되었을 때, a와 연결된 도시들의 집합과 b와 연결된 도시들의 집합을 합친다.

+Kruskal의 최소 스패닝 트리(Minimum Spanning Tree) 알고리즘

📝예제::가장 큰 집합 추적하기

각 집합에 속한 원소의 수를 추적하는데 구간 트리를 사용할 수 있다.

집합들이 합쳐지는 과정에서 가장 큰 집합의 크기가 어떻게 변하는지 추적하거나 과반수가 출현하는 시점을 찾는 문제도 구간트리로 해결할 수 있다.

⚡️keypoint⚡️

1. 각 트리의 노드의 개수를 담는 배열 size[]를 추가한 뒤 두 집합이 합쳐질 때마다 값을 갱신해준다.

📝예제::에디터 전쟁(ID: EDITORWARS)

두 종류의 편집기가 있다. 각 편집기에 대해 쓴 댓글로 이 사람이 어떤 편집기를 사용하는지 유추하여 해당 편집기모임에 초대하려고 한다. 이 때, 한 파티에 참여하는 가능한 최대 인원을 계산하는 문제.

상호 인정 댓글은 ACK a b 형태로, 상호 비방 댓글은 DIS a b 형태로 입력이 주어진다.

⚡️keypoint⚡️

1. (원칙 1) 내가 상대방과 같은 편집기를 사용할 때, 상대방과 다른 편집기를 쓰는 사람은 나와도 다른 편집기를 사용한다.
2. (원칙 2) 내가 상대방과 다른 편집기를 사용할 때, 상대방과 다른 편집기를 쓰는 사람은 나와 같은 편집기를 사용한다.

⌨️에디터 전쟁 문제를 해결하는 상호 배타적 집합

parent[i] = i : i의 부모노드. 만약, i가 루트인 경우 parent[i] 는 자기 자신이다.

rank[i] : i가 루트인 경우, i를 루트로 하는 트리의 랭크(= 높이)

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

size[i] : i가 루트인 경우, 해당 집합의 크기(= 원소의 개수)

struct BipartiteUnionFind {
  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]); //루트 아니면, u의 부모노드의 루트 반환
  }
  int merge(int u, int v) {
    if(u==-1 || v==-1) //u와 v가 공집합이라면 둘 중에 큰 거 반환
      return max(u,v); 
    u = find(u); v = find(v);
    if(u==v) //u와 v가 이미 같은 집합에 있다면, 둘 중 하나인 u 반환(v도 됨)
      return u; 
    if(rank[u] > rank[v]) //만약 u의 트리높이가 더 높다면, 바꿔준다.(u가 더 크지않도록)
      swap(u,v);
    //현재 u의 트리 높이가 v의 트리 높이보다 작거나 같은 상태이다. 
    //u와 v의 트리높이가 같다면, v의 높이를 +1해준다.(그림그리면 이해쉽다)
    if(rank[u] == rank[v]) rank[v]++;
    parent[u] = v; //u의 부모노드를 v로 설정
    size[v] += size[u]; //원소의 개수 갱신
    return v;
  }
  //u와 v가 서로 적대관계일 때, 모순유무에 따라 처리해주는 함수
  int dis(int u, int v) {
    u = find(u); v = find(v); //일단 루트 찾아주고
    if(u == v) return false; //적대관계인데 같은 집합에 속해있으면 모순
    int a = merge(u, enemy[v]);//'u'와 'v와 적대관계에 있는 사람들'을 합친다. 
    int b = merge(v, enemy[u]);//'v'와 'u와 적대관계에 있는 사람들'을 합친다. 
    enemy[a] = b; //집합 b가 a의 적대관계에 있는 사람들의 집합이 되도록 설정 
    enemy[b] = a; //집합 a가 b의 적대관계에 있는 사람들의 집합이 되도록 설정
    return true;
  }
  //u와 v가 서로 같은 집합일 때(같은 에디터 사용 시), 모순 처리해주는 함수
  //모순; u와 v가 다른 집합에 속할 때
  //원칙; u가 v가 같은 집합이므로 u의 적대관계 집합은 v의 적대관계 집합과 같다.
  int ack(int u, int v) {
    u = find(u), v = find(v); //루트 찾아주고
    if(enemy[u] == v) return false; //모순
    int a = merge(u,v); //a에는 u와 v를 합치고
    int b = merge(enemy[u], enemy[v]); //원칙에 따라, u,v에 적대관계 집합을 합친다.
    enemy[a] = b; //집합 b가 a의 적대관계집합이 되도록 설정 
    //두 집합 다 적대하는 집합이 없으면(= enemy[u]와 enemy[v]가 공집합이면) b=-1 
    if(b != -1) enemy[b] = a; 
    return true;
  }
};

int maxParty(const BipartiteUnionFind& buf) {
  int ret = 0;
  for(int node=0; node<n; ++node) { //n:전체 회원의 수
    if(buf.parent[node] == node) {//node가 루트이면
      int enemy = buf.enemy[node];//node와 적대관계에 있는 사람을 enemy라고 하고
      if(enemy > node) continue; //중복을 방지하기 위한 코드
      int mySize = buf.size[node];//node의 집합크기를 mySize라고 하고
      //적대관계에 있는 사람이 없다면 집합크기를 0으로, 아니라면 그 수만큼 enemySize 설정
      int enemySize = (enemy==-1 ? 0 : buf.size[enemy]);
      ret += max(mySize, enemySize);//최대인원수 갱신
    }
  }
  return ret;
}