[코딩 테스트 합격자 되기 문제 33] 간단한 유니온-파인드 알고리즘 구현하기

문제 설명

상호배타적 집합을 표현하고 관리하는 데 다음 두 연산이 필요합니다.

• union(x,y) : x와 y가 속한 두 집합을 합칩니다.
• find(x,y) : x가 속한 집합의 대표 원소를 찾습니다.

operations라는 배열은 수행할 연산을 의미합니다. 연산 종류는 2개입니다.

• ['u',1,2]는 노드 1과 노드 2에 대해 union 연산 수행
• ['f',3]는 노드 3의 루트 노드 찾기, find 연산 수행

초기의 노드는 부모 노드를 자신의 값으로 설정했다고 가정하며, 여기서는 각 집합의 루트 노드를 기준으로 루트 노드가 작은 노드를 더 큰 노드의 자식으로 연결하는 방법을 사용합니다. operations에 있는 연산을 모두 수행한 후 집합의 개수를 반환하는 solution() 함수를 구현해주세요.

 

제약 조건

• 0 <= k <= 1000 : 노드의 개수
• 1 <= operations <= 100000
• operations[i][0]은 문자열 'u' 또는 'f' 중 하나
• 'u'는 union 연산, union 연산 뒤로는 두 개의 정수 x,y가 나옴
• 'f'는 find 연산, find 연산 뒤로는 하나의 정수 x가 나옴
• x와 y는 0 이상 k-1 이하의 정수
• 연산은 항상 유효함
  • 즉, union, find 연산의 인수는 상호배타적 집합 내에 있는 노드 번호

입출력의 예

k	operations	result
3	[['u', 0, 1], ['u',1, 2],['f', 2]	1
4	[['u', 0, 1], ['u',2, 3],['f', 0]	2

 

정답

const find = (parents, x) => {
    //루트 노드를 찾는 것
    if(parents[x] === x){
	//parents[x]가 x의 부모 노드니깐 같으면 루트 노드를 찾은거니깐
	return x;
    }
    
    parents[x] = find(parents, parents[x]); //부모 노드의 부모 노드의 부모 노드의...
    //재귀로 찾아낸다
    return parents[x];
}

const union = (parents, x, y) = {
    //합치는거 => 루트 노드를 같게 하는것
    //우선 루트 노드를 찾고 합치면 된다
    const root1 = find(parents, x);
    const root2 = find(parents, y);
    
    parents[root2] = root1; //x가 속한 집합의 루트 노드랑 같게 하는거니깐 y가 x에 붙음
}


const solution = (k, operations) => {
    //자기를 루트 노드로 초기화
    //[0,1,2]
    const parents = Array.from({length: k}, (_,i) => i);
    let n = k; //집합의 개수, 지금은 다 다른 집합이니깐(루트 노드가 다르니깐) k개
    
    for(const op of operations){
    	if(op[0] === 'u'){
        	union(parents, op[1], op[2]);
        }else if(op[1] === 'f'){
        	find(parents, op[1]);
        }
    }
    
    //루트 노드의 갯수가 곧 집합의 갯수
    n = new Set(Array.from({length: k}, (_,i) => find(parents,i))).size;
    
    return n;
}