문제
풀이
요구사항
N개의 노드가 있고, M개의 간선 정보가 주어졌을 때, 이를 트리로 만들기 위해 간선을 연결하거나, 끊는 연산을 할 수 있다.
이때 트리를 만들기 위해 필요한 최소 연산 횟수를 구하시오.
트리란 사이클이 발생하지 않고 모든 노드가 연결되어 있는 자료구조를 말한다.
해결방안
최소 연산 횟수로 트리를 만들어줘야 하고, 이 트리는 사이클이 발생하면 안된다.
사이클이 발생하는지 유무는 어떻게 확인할 수 있을까?
간선을 연결할 때 "유니온 파인드"를 통해 두 노드의 부모 노드가 같을 경우 사이클이 발생하는 것이고, 부모 노드가 다를 경우 사이클이 발생하지 않는 것임을 알 수 있다.
이를 통해 간선을 연결할 때, 연결 끊기 연산의 횟수를 구할 수 있다.
연결 끊기 연산
만약 두 노드를 연결하려는데 부모 노드가 같다면, 연결을 수행하지 않고 연결 끊기 연산의 횟수를 1 증가시킨다.
예를 들어 간선의 정보가 아래와 같이 주어졌을 경우
1 2
1 3
2 3 <- 사이클 발생
2번과 3번을 연결하면 사이클이 발생하기 때문에 연결을 수행하지 않고, 연결 끊기 연산 횟수를 1 증가시킨다.
function unionFind() {
for (let i = 0; i < M; i++) {
const a = find(arr[i][0]);
const b = find(arr[i][1]);
// 연결할 경우 사이클이 발생한다면
if (a === b) cut++; // 연결 끊기 연산
else union(a, b);
}
}연결 연산
연결 연산의 횟수는 어떻게 구할 수 있을까?
입력이 아래와 같이 주어졌다고 가정해보자.
6 4
1 2
1 3
4 5
4 6이를 유니온 파인드를 통해 연결해주면 아래와 같이 두개의 서브 트리가 만들어진다.
각각의 서브 트리당 루트 노드는 하나씩 있고, 위 그림에서는 1과 4가 각각의 서브 트리의 루트노드다.
루트노드는 parent[i] === i 라는 특징이 있다. 즉, 부모 노드와 자기 자신의 번호가 같다.
이러한 점을 이용해서 부모 노드와 자기 자신의 번호가 같은 노드를 발견할 경우 연결 연산을 수행해준다.
for (let i = 1; i <= N; i++) {
if (parent[i] === i) connect++;
}단,parent[i] === i인 노드가 한 개밖에 없을 경우에는 모든 노드가 하나의 트리에 포함되어 있는 것이기 때문에 연결 연산을 수행할 필요가 없다.
하지만 위의 코드에서는 루트 노드의 개수만큼 연결 연산 횟수를 증가시키기 때문에 최종적으로 답을 출력할 때는 connect에서 1을 빼줘야 한다.
console.log(cut + connect - 1);좀 더 직관적인 방법은 아래처럼 코드를 작성해서 모든 노드의 루트 노드가 동일한지 확인하고 루트 노드가 동일하지 않다면 카운트를 증가시키는 방법도 있다.
const root = find(1);
for (let i = 2; i <= N; i++) {
const sub = find(i);
if (root !== sub) {
union(root, sub);
connect++;
}
}
console.log(cut + connect);최종 코드
const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [N, M] = input[0].split(' ').map(Number);
const arr = input.slice(1, 1 + M).map((e) => e.split(' ').map(Number));
const parent = Array.from({ length: N + 1 }, (_, i) => i);
let cut = 0;
let connect = 0;
function unionFind() {
for (let i = 0; i < M; i++) {
const a = find(arr[i][0]);
const b = find(arr[i][1]);
// 연결할 경우 사이클이 발생한다면
if (a === b) cut++; // 연결 끊기 연산
else union(a, b);
}
}
function union(a, b) {
if (a < b) parent[b] = a;
else parent[a] = b;
}
function find(x) {
if (parent[x] !== x) parent[x] = find(parent[x]);
return parent[x];
}
unionFind();
for (let i = 1; i <= N; i++) {
if (parent[i] === i) connect++;
}
console.log(cut + connect - 1);
시행착오
연결 연산의 횟수를 구하는 과정에서 Set함수를 사용해서 구하려고 코드를 아래와 같이 작성했었다.
const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [N, M] = input[0].split(' ').map(Number);
const arr = input.slice(1, 1 + M).map((e) => e.split(' ').map(Number));
const parent = Array.from({ length: N + 1 }, (_, i) => i);
let cut = 0;
function unionFind() {
for (let i = 0; i < M; i++) {
const a = find(arr[i][0]);
const b = find(arr[i][1]);
// 연결할 경우 사이클이 발생한다면
if (a === b) cut++; // 연결 끊기 연산
else union(a, b);
}
}
function union(a, b) {
a = find(a);
b = find(b);
if (a < b) parent[b] = a;
else parent[a] = b;
}
function find(x) {
if (parent[x] !== x) parent[x] = find(parent[x]);
return parent[x];
}
unionFind();
const set = new Set(parent);
console.log(cut + set.size - 2);하지만 이럴 경우 아래와 같은 반례가 존재한다.
3 2
2 3
1 2
correct answer: 0
wrong answer: 1이런 문제가 발생하는 이유는, parent[i]에는 루트 노드의 번호가 아니라 직속 부모 노드의 번호가 들어있기 때문이다.
2 3 에서 2번과 3번이 연결되고, 1 2로 1번과 2번이 연결되면서 사실은 1,2,3번이 모두 연결되어 있지만, parent는 아래와 같기 때문에 그냥 Set함수로 중복만 제거해서는 오답이 나오는 것이다.
| parent | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | 1 | 1 | 2 |
