[백준/JS] 4195 친구 네트워크

 

문제링크: https://www.acmicpc.net/problem/4195

4195번: 친구 네트워크

 

유니온 파인드 문제이다.

문제 종류를 알고 풀었는데도 쉽지 않아 해설을 보았다.

 

1. parent 배열과 relation 배열을 선언한다.

  1-1. parent 배열은 기존의 유니온 파인드 방식처럼, 배열[index] = index 로 초기화한다.

  1-2. relation 배열은 유니온 될때 서로의 친구관계의 수를 합하기 위해 선언된다. 모두 1로 초기화한다.

  1-3. 배열의 범위는 200_001 인데 그 이유는 친구관계가 100_000 이므로 100_000 * 2 = 200_000 이기 때문이다.

 

2. idx = 1 로 선언하여 새로운 친구가 나올때 hash[친구이름] = idx ++ 를 해준다. 여기서 parent 배열과 hash 맵을 통해 서로 연결하는 것을 보고 감탄했다. 

 

3. 나머지는 기본 유니온 파인드와 동일한데, merge함수(Union) 부분에서 relation[V] += relation[U] 를 해준다.

왜 relation[V] 에 더한값을 저장하냐라고 생각할 수 있는데 V 가 루트가 될 노드이기 때문이다. 고로 Find 를 했을 때 나오는 루트의 relation 배열 값을 갱신해주어야한다.

 

const fs = require("fs");

BOJkey = true;

const input = fs
  .readFileSync(BOJkey ? "./ehddud1006/BOJ/4195/input.txt" : "./dev/stdin")
  .toString()
  .trim()
  .split("\n")
  .reverse();

let T = Number(input.pop());
let answer = [];
let parent;
let relation;

while (T--) {
  const N = Number(input.pop());
  let idx = 1;
  const hash = {};
  parent = Array.from({ length: 200001 }, (_, i) => i);
  relation = Array.from({ length: 200001 }, () => 1);

  for (let i = 0; i < N; i++) {
    const [a, b] = input.pop().split(" ");

    if (hash[a] === undefined) hash[a] = idx++;
    if (hash[b] === undefined) hash[b] = idx++;

    let ai = hash[a];
    let bi = hash[b];

    merge(ai, bi);
  }
}

function find(u) {
  if (u === parent[u]) return u;

  return (parent[u] = find(parent[u]));
}

function merge(u, v) {
  let U = find(u);
  let V = find(v);

  if (U === V) {
    answer.push(`${relation[U]}`);
    return;
  }

  parent[U] = V;
  relation[V] += relation[U];
  answer.push(`${relation[V]}`);
}

console.log(answer.join("\n"));

 

시간 복잡도 : O(T * N * Log N)