해당 포스팅은 백준 1717번 집합의 표현 풀이를 다룬다. 문제 링크
코드는 javascript로 작성하였다.
문제
1. 문제 설명
초기에 {0}, {1}, {2}, ... {n} 이 각각 n+1개의 집합을 이루고 있다.
여기에 합집합 연산과, 두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산을 수행하려고 한다.
집합을 표현하는 프로그램을 작성하시오.
2. 입력
-
첫째 줄에
n(1 ≤ n ≤ 1,000,000),m(1 ≤ m ≤ 100,000)이 주어진다. m은 입력으로 주어지는 연산의 개수이다. 다음 m개의 줄에는 각각의 연산이 주어진다. -
합집합
0 a b의 형태- a가 포함되어 있는 집합과, b가 포함되어 있는 집합을 합친다는 의미
-
두 원소가 같은 집합에 포함되어 있는지를 확인하는 연산
1 a b의 형태- a와 b가 같은 집합에 포함되어 있는지를 확인하는 연산
- 0 ≤ a, b ≤ n
3. 출력
1로 시작하는 입력에 대해서 한 줄에 하나씩 YES/NO로 결과를 출력한다. (yes/no 를 출력해도 된다)
풀이
유니온 파인드 구현 문제였다. 0이 입력되면 union, 1이 입력되면 find 연산을 하면 된다.
필자는 배열로 풀이했으나 유니온 파인드는 트리 문제이므로 다른 사람이 푼 트리 풀이또한 리뷰하고자 한다.
풀이에 사용된 함수
1. 초기화
n이 5일 때 0 ~ 5까지 6개의 노드를 만들어야 한다. 처음 6개의 노드는 무분별하게 존재한다고 가정한다. 모두 연결되지 않고 각각 자기 자신을 부모노드로 갖는다.
이를 코드로 아래와 같이 표현할 수 있다.
const arr = new Array(n+1).fill(0).map((_, i) => i);2. root 노드를 찾는 재귀함수 정의
해당 함수는 union, find 함수에서 사용되는 함수이다. 노드 n을 인자로 받으며 해당 노드가 루트 노드인지 판별한다.
arr[n] === n일 시 n의 root 노드가 자기 자신이므로, return n을 하여 find 함수를 탈출한다.arr[n] !== n일 시 자기 자신이 root 노드가 아니므로 재귀를 통해 자신의 트리에서 루트 노드를 찾으러 간다. 이 때 경로 압축을 해 트리에 부모노드를 하나만 갖게끔 만든다.
아래 그림을 보면서 해당 함수 로직을 이해해보자.
먼저 노드들 중 0,1,4와 3,5가 한 트리로 합쳤다고 가정하자.
이 때 노드 3과 4를 합친다고 가정하자. 아래에서 설명하겠지만 union할 때 두 노드 중 부모 노드 값이 더 작은 값으로 합칠 것이다. 따라서 3,4 트리는 0, 1, 4 트리에 합쳐지게 된다.
이 때 0, 1, 4, 3, 4는 모두 같은 트리이므로 부모 루트를 계속 연결시키는 것이 아닌 최상단의 노드를 부모로 정한다. 즉 아래처럼 0을(트리에서 가장 작은 값이므로) root 노드로 정한다. 이를 경로 압축이라고 부른다 (트리 depth가 2로 유지된다).
이를 코드로 아래와 같이 표현할 수 있다.
// root 노드를 찾는 재귀 함수
function getParent(arr, n) {
// 자기 자신이 root노드일 시
if (arr[n] === n) return n;
// root노드가 아닐 시 자신의 트리에서 root를 찾기 위해 재귀한다
// 이 때 경로 압축을 해 트리에 부모노드를 하나만 갖게끔 만든다
return (arr[n] = getParent(arr, arr[n]));
}3. 2개의 노드가 같은 부모 노드를 가졌는지 확인하는 find 함수
위에서 정의한 getParent 함수를 이용해 두 노드가 같은 부모(root) 노드를 갖고 있는지를 판별한다. 같으면 YES, 다르면 NO를 리턴한다.
이를 코드로 아래와 같이 표현할 수 있다.
function findParent(arr, a, b) {
const n1 = getParent(arr, a);
const n2 = getParent(arr, b);
// 같을 시 YES, 다를 시 NO
if (n1 === n2) return "YES";
else return "NO";
}4. 두 개의 노드를 같은 부모 노드로 병합하는 union 함수
두 개의 노드 중 부모 노드가 더 작은 값으로 합친다.
위의 예시를 다시금 살펴보자.
0, 1, 4와 3, 5 트리는 각각 root 노드를 0, 3으로 갖고 있다(union할 때 작은 노드 값을 root 노드로 하기 때문이다).
이 때 3과 4를 union한다면, 3의 root 노드는 3, 4의 root 노드는 0이다. 따라서 0을 root 노드로 하고 두 트리를 병합한다. 이 때 경로압축으로 depth는 2가 된다.
이를 코드로 아래와 같이 표현할 수 있다.
function unionParent(arr, a, b) {
const n1 = getParent(arr, a);
const n2 = getParent(arr, b);
// 두 노드 중 부모 노드 값이 더 작은 값으로 합친다.
if (n1 < n2) arr[n2] = n1;
else arr[n1] = n2;
}전체 코드 (배열 풀이)
const readline = require('readline');
const input = [];
readline.createInterface({
input: process.stdin,
output: process.stdout
}).on('line', (line) => {
input.push(line.split(' ').map(elem => +elem));
}).on('close', () => {
solution();
process.exit();
});
// 정답 출력 함수
function solution() {
const [n,m] = input.shift();
const answer = [];
// 초기화 과정
const arr = new Array(n+1).fill(0).map((_, i) => i);
// m개의 연산 수행
for (let el of input) {
const [cmd, node1, node2] = el;
// cmd가 0이면 union
if (cmd === 0) {
unionParent(arr, node1, node2)
}
// cmd가 1이면 find
else {
const test_result = findParent(arr, node1, node2);
answer.push(test_result);
}
}
console.log(answer.join("\n"))
}
// root 노드를 찾는 재귀 함수
function getParent(arr, n) {
// 자기 자신이 root노드일 시
if (arr[n] === n) return n;
// root노드가 아닐 시 자신의 트리에서 root를 찾기 위해 재귀한다
// 이 때 경로 압축을 해 트리에 부모노드를 하나만 갖게끔 만든다
return (arr[n] = getParent(arr, arr[n]));
}
// 두 개의 노드를 같은 부모 노드로 병합하는 union 함수
function unionParent(arr, a, b) {
const n1 = getParent(arr, a);
const n2 = getParent(arr, b);
// 두 노드 중 부모 노드 값이 더 작은 값으로 합친다.
if (n1 < n2) arr[n2] = n1;
else arr[n1] = n2;
}
// 2개의 노드가 같은 부모 노드를 가졌는지 확인하는 find 함수
function findParent(arr, a, b) {
const n1 = getParent(arr, a);
const n2 = getParent(arr, b);
// 같을 시 YES, 다를 시 NO
if (n1 === n2) return "YES";
else return "NO";
}다른 사람 풀이 - 트리 구현
아래는 다른 사람 풀이로, 트리를 구현한 풀이다. 로직은 동일하지만 필자는 findParent를 따로 함수로 빼서 YES, NO를 판별했으나, 아래 풀이는 solution에서 판별했다는 차이점이 있다.
const readline = require('readline');
const input = [];
readline.createInterface({
input: process.stdin,
output: process.stdout
}).on('line', (line) => {
input.push(line.split(' ').map(elem => +elem));
}).on('close', () => {
solution();
process.exit();
});
class Tree {
constructor(n) {
this.parent = new Array(n+1)
.fill(0)
.map((_, i) => i);
}
union(n1, n2) {
const a = this.find(n1);
const b = this.find(n2);
if (a < b) this.parent[b] = a;
else this.parent[a] = b;
}
find(node) {
if (this.parent[node] === node) {
return node;
}
this.parent[node] = this.find(this.parent[node]);
return this.parent[node];
}
}
function solution() {
const [n,m] = input.shift();
const tree = new Tree(n);
const answer = [];
for (let el of input) {
const [a, b, c] = el;
if (a === 0) {
tree.union(b, c)
}
else {
if (tree.find(b) === tree.find(c)) {
answer.push("YES");
} else {
answer.push("NO")
}
}
}
console.log(answer.join("\n"))
}/dev/stdin 런타임 에러?
해당 문제는 node.js로 풀 때 /dev/stdin을 사용할 경우 런타임 에러 (EACCES)가 발생한다. readline으로 고치면 해결된다.
위의 글은 백준 질문 게시판의 공지를 확인하면 된다.
평소 /dev/stdin로 풀었는데, 계속 런타임 에러 (EACCES)가 떠서 삽질을 했다 ㅠㅠ... 다른 분들은 해당 부분으로 삽질을 안 하길 바란다.
