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

종만북 25장 상호 배타적 집합

이 포스팅은 <프로그래밍 대회에서 배우는 알고리즘 문제 해결 전략>, 구종만, 인사이트(2012)을 읽고 개인 학습용으로 정리한 글입니다.

➖ 21-08-30

트리를 이용한 상호 배타적 집합의 표현

//트리를 이용한 (단순한) 상호 배타적 집합 자료 구조의 표현
struct NaiveDisjointSet{
	vector<int> parent;
	NaiveDisjointSet(int n): parent(n){
		//n개의 원소가 각각의 집합에 표현되어 있도록 초기화
		for(int i = 0; i < n; ++i)
			parent[i] = i;
	} 
	//u가 속한 트리의 루트 번호 반환
	int find(int u) const{
		//부모가 자기 자신을 가리키는 경우 u는 루트 노드
		if(u == parent[u]) return u;
		return find(parent[u]);
	}
	//u가 속한 트리와 v가 속한 트리를 합친다
	void merge(int u, int v){
		u = find(u); v = find(V);
		//u와 v가 이미 같은 트리에 속하는 경우 return
		if(u == v) return;
		//v를 루트로 하는 트리의 자손으로 u를 루트로 하는 트리를 넣는다
		parent[u] = v;
	}
};

상호 배타적 집합의 최적화

• 랭크에 의한 합치기(union-by-rank) 최적화
  -> rank[]: 해당 노드가 트리의 루트인 경우 해당 트리의 높이 저장
  (⚡경로 압축 최적화를 적용하면 이 값은 트리의 높이와 별 상관 없어진다)
  -> 두 트리를 합칠 때 항상 높이가 더 낮은 트리를 더 높은 트리 밑에 집어 넣음으로써 트리의 높이가 높아지는 상황을 방지한다
  -> 두 트리의 높이가 같은 경우에만 결과 트리의 높이를 1 늘려준다

• 경로 압축(path compression) 최적화
  -> find(u)를 통해 u가 속하는 트리의 루트를 찾아냈을 때, parent[u]를 찾아낸 루트로 바꿔버리면
  다음번에 find(u)가 호출되었을 때 경로를 따라 올라갈 것 없이 바로 루트를 찾을 수 있다
  -> 재귀적인 구현 덕분에 find(u)를 호출하면 u에서 루트까지 올라가는 경로 상에 있는 모든 노드들에도 경로 압축 최적화가 자동으로 수행된다

//최적화된 상호 배타적 집합의 구현
struct OptimizedDisjointSet{
	vector<int> parent, rank;
	OptimizedDisjointSet(int n): parent(n), rank(n,1){
		//n개의 원소가 각각의 집합에 표현되어 있도록 초기화
		for(int i = 0; i < n; ++i)
			parent[i] = i;
	} 
	//u가 속한 트리의 루트 번호 반환
	int find(int u) {
		//부모가 자기 자신을 가리키는 경우 u는 루트 노드
		if(u == parent[u]) return u;
        //경로 압축(path compression) 최적화 구현
		return parent[u] = find(parent[u]);
	}
	//u가 속한 트리와 v가 속한 트리를 합친다
	void merge(int u, int v){
		u = find(u); v = find(v);
		//u와 v가 이미 같은 트리에 속하는 경우 return
		if(u == v) return;
		//랭크에 의한 합치기(union-by-rank) 최적화 구현
		if(rank[u] > rank[v]) swap(u, v);
		//rank[v]가 항상 rank[u] 이상이므로
		//v를 루트로 하는 트리의 자손으로 u를 루트로 하는 트리를 넣는다
		parent[u] = v;
		//rank[u]와 rank[v]가 같은 경우 결과 트리의 높이를 1 늘려준다
		if(rank[u] == rank[v]) ++rank[v];
	}
};

에디터 전쟁(EDITORWARS)

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

• 동지의 적은 나의 적이다
  : 나와 상대가 같은 편집기를 쓴다면, 상대와 다른 편집기를 쓰는 사람(동지의 적)은 나와 다른 편집기를 쓴다(나의 적)
  적의 적은 나의 동지다
  : 나와 상대가 다른 편집기를 쓴다면, 상대와 다른 편집기를 쓰는 사람(적의 적)은 나와 같은 편집기를 쓴다(나의 동지)

• ⚡각 집합 간의 적대 관계를 그림으로 그려보면 항상 이분 그래프(Bipartite Graph)를 이룬다

구현하기

• 상호 배타적 집합에 다른 정보를 추가해서 새로운 연산을 지원할 수 있다

//에디터 전쟁 문제를 해결하는 상호 배타적 집합의 구현
struct BipartiteUnionFind{
	//parent[i]: i의 부모 노드, i가 루트 노드일 경우 parent[i] = i
	//rank[i]: i를 루트로 하는 트리의 랭크, i가 루트인 경우 rank[i] = 1
	//enimy[i]: i가 루트인 경우, 해당 집합과 적대 관계인 집합의 루트의 번호(없으면 -1)
	//size[i]: i가 루트인 경우, 해당 집합의 크기
	vector<int> parent, rank, enimy, size;
	BipartiteUnionFind(int n): parent(n), rank(n, 0), enimy(n, -1), size(n, 1){
		for(int i = 0; i<n; ++i)
			parent[i] = i;
	}
    int find(int u){
    	if(u == parent[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);
		//u와 v가 이미 같은 트리에 속하는 경우 return
		if(u == v) return u;
		
		if(rank[u] > rank[v]) swap(u, v);
		parent[u] = v;
		if(rank[u] == rank[v]) ++rank[v];
		
		size[v] += size[u];
		return v;
	}
	
	//상호 비방(u와 v가 서로 적이다): 모순이 일어났다면 false, 아니면 true 반환
	bool dis(int u, int v){
		//우선 루트를 찾는다
		u = find(u); v = find(v);
		
		//1. 모순 확인하기
		//모순인 경우: u와 v가 같은 편집기를 사용하고 있는 경우
		if(u == v) return false;
		
		//2. "적의 적은 나의 동지다"
		//u와 v에 적대적인 집합을 합쳐 준다
		int a = merge(u, enimy[v]);
		//v와 u에 적대적인 집합을 합쳐 준다
		int b = merge(v, enimy[u]);
		
		//3. 결과적으로 얻은 두 집합을 서로 적대 관계로 설정한다
		enimy[a] = b;
        enimy[b] = a;
		
		return true;
	}
	//상호 인정(u와 v가 서로 동지다): 모순이 일어났다면 false, 아니면 true 반환
	bool ack(int u, int v){//우선 루트를 찾는다
		u = find(u); v = find(v);
		
		//1. 모순 확인하기
		//모순인 경우: u와 v가 서로 적대 관계에 있는 경우
		if(enimy[u] == v) return false;
		
		//2. "동지의 적은 나의 적이다"
		//u와 v를 합쳐 준다
		int a = merge(u, v);
		//u에 적대적인 집합과 v에 적대적인 집합을 합쳐 준다
		int b = merge(enimy[u], enimy[v]);
		
		//3. 결과적으로 얻은 두 집합을 서로 적대 관계로 설정한다
		enimy[a] = b; 
		//두 집합 모두 적대적인 집합이 없으면 b는 -1일 수 있다
		if(b != -1) enimy[b] = a;
		
		return true;
		}
};

• 각 집합들에 대한 정보를 찾고 나면 원 문제에 대한 답을 간단하게 구할 수 있다
  -> 적대 괸계인 각 집합 쌍에 대해 더 큰 쪽의 크기들을 모두 더한다

• 각 집합 쌍을 정확히 한 번만 세기 위해 enimy<node인 경우만 센다
  -> ⚡enimy == -1인 경우도 정확히 한 번씩 세게 된다
  -> 적대 집합이 없는 경우도 예외 처리 없이 구현할 수 있다
  

//상호 배타적 집합이 주어질 때 에디터 전쟁 문제의 답을 구하는 함수의 구현

//BipartiteUnionFind 인스턴스가 주어질 때
//한 파티에 올 가능성이 있는 최대 인원을 구한다
int maxParty(const BipartiteUnionFind& buf){
	int ret = 0;
	for(int node = 0; node < n; ++node){
		if(buf.parent[node] == node){
			int enimy = buf.enimy[node];
			
			if(enimy > node) continue;
			
			int mySize = buf.size[node];
			int enimySize = (enimy == -1? 0 : buf.size[enimy]);
			//적대 관계인 집합 쌍에서 더 큰 쪽의 크기를 더한다
			ret += max(mySize, enimySize);
		}
	}
	return ret;
}