🔴 문제
🟡 Sol
const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const inputs = fs.readFileSync(0, 'utf-8').trim().split('\n');
const [n, m] = inputs[0].split(' ').map(Number);
const p = Array.from({ length: n + 1 }).map((_, idx) => idx);
const find = (a) => {
if (p[a] !== a) {
p[a] = find(p[a]);
}
return p[a];
};
const union = (a, b) => {
const pA = find(a);
const pB = find(b);
p[pB] = pA;
};
for (let i = 1; i <= m; i++) {
const [op, a, b] = inputs[i].split(' ').map(Number);
if (op) {
console.log(find(a) === find(b) ? 'YES' : 'NO');
} else {
union(Math.min(a, b), Math.max(a, b));
}
}
🟢 풀이
⏰ 소요한 시간 : -
유니온 & 파인드 문제 기본유형이다. 유니온 & 파인드 알고리즘을 먼저 학습해야 한다. 아래 유튜브를 통해 학습할 수 있다.
n+1개의 집합 p를 만들어 준 뒤, 1부터 연산의 개수인 m만큼 반복하며 유니온이나 파인드 연산을 진행해주면 된다.
만약 op가 1인경우 두 원소가 같은 집합에 포함되어 있는지를 확인해야하는데 이는 find를 사용하면 되고, op가 0인 경우 a가 포함되어 있는 집합과 b가 포함되어 있는 집합을 합쳐주는 즉 union 연산을 하면 된다.
union과 find 함수 내부를 구현해보자.
find 함수는 내가 어떤 집합에 속해있는지, 내가 속한 집합의 대표요소를 찾는 함수이다. 대표요소는 인덱스인 a와 p[a]의 값이 동일한 요소가 된다. 따라서 p[a]와 a가 동일할 경우에만 p[a]를 리턴해주고, 그게 아니라면 재귀적으로 find 함수를 호출하여 대표오소를 찾을 수 있도록 한다.
union 함수는 find 함수를 사용하여 두 원소의 부모를 찾고, pB의 부모를 pA로 바꾸면 된다. pA의 부모를 pB로 바꿔도 된다.
🔵 Ref
록타르오가르