[백준] 2606 바이러스

이 문제는 bfs나 dfs를 이용하는게 더 편한 문제다. union find 연습을 위해서 union find로 해결해 보았다.

let fs = require("fs");
const { cachedDataVersionTag } = require("v8");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
// let input = fs.readFileSync("./input.text").toString().split("\n");

let node = Number(input[0]);
let vertexs = input.slice(2);
const parent = [0];
for (let i = 1; i <= node; i++) {
  parent.push(i);
}

vertexs.map((ele) => {
  let vertex = ele.split(" ");
  union(Number(vertex[0]), Number(vertex[1]));
});

let cnt = 0;
for (let i = 2; i < parent.length; i++) {
  if (parent[i] === 1) {
    cnt++;
  }
}
console.log(cnt);

// 가장 상위 조상을 찾는다.
function find(x) {
  if (x === parent[x]) {
    return x;
  } else {
    let y = find(parent[x]);
    parent[x] = y;
    return y;
  }
}

// 조상끼리 이어주는 역할
function union(x, y) {
  x = find(x);
  y = find(y);
  if (x <= y) {
    parent[y] = x;
  } else {
    parent[x] = y;
  }
}

그리고 이렇게 제출하면 틀린다.

왜?
위 코드에서는 자식들이 내 조상이 누구랑 이어져 있는지 모르는 경우가 발생한다.

위 그림을 보면 문제 상황에 대해 알 수 있는데 y가 1이라고 한다면 문제에서 답은 5겠지만 틀린 코드에서는 2가 나오게 된다. 그래프를 완성시킨 다음 지금 내가 알고 있는 조상 정보가 진짜 가장 상위 조상으로 업데이트 되었는지 확인해야 한다.

let fs = require("fs");
const { cachedDataVersionTag } = require("v8");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
// let input = fs.readFileSync("./input.txt").toString().split("\n");

let node = Number(input[0]);
let vertexs = input.slice(2);
const parent = [0];
for (let i = 1; i <= node; i++) {
  parent.push(i);
}

vertexs.map((ele) => {
  let vertex = ele.split(" ");
  union(Number(vertex[0]), Number(vertex[1]));
});

// 조상 정보 업데이트
for (let i = 1; i <= node; i++) {
    parent[i] = find(i);
}

let cnt = 0;
for (let i = 2; i <= node; i++) {
  if (parent[i] === 1) {
    cnt++;
  }
}
console.log(cnt);

function find(x) {
  if (x === parent[x]) {
    return x;
  } else {
    let y = find(parent[x]);
    parent[x] = y;
    return y;
  }
}

function union(x, y) {
  x = find(x);
  y = find(y);
  if (x <= y) {
    parent[y] = x;
  } else {
    parent[x] = y;
  }
}

위 코드와 같이 조상 최종적으로 조상 정보를 업데이트 해주는 코드를 추가하면 정답이 된다.