[백준] 16562번: 친구비 (JavaScript)

 

 

---

 

문제

https://www.acmicpc.net/problem/16562

 

개념

그래프, 분리 집합, 유니온 파인드 

 

 

구현 코드(JavaScript)

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');
const [n, m, k] = input[0].split(' ').map((i) => +i);
const friendCost = input[1].split(' ').map((i) => +i); // 친구비 입력
const friendRelation = input // 친구 관계 [v, w] 입력
  .slice(2)
  .map((real) => real.split(' ').map((i) => +i));
const parent = Array.from({ length: n + 1 }, (_, i) => i);

// union-find
const make = () => {
  for (let i = 1; i <= n; i++) {
    parent[i] = i;
  }
};
const find = (a) => {
  if (parent[a] === a) return a;
  return (parent[a] = find(parent[a]));
};
const union = (a, b) => {
  const rootA = find(a);
  const rootB = find(b);
  if (rootA !== rootB) {
    parent[rootB] = rootA;
    return true;
  }
  return false;
};

make();
for (let i = 0; i < m; i++) {
  const [v, w] = friendRelation[i];
  union(v, w);
}

const cost = Array.from({ length: n + 1 }, () => 1e9); // 학생 별 최소 친구비
let minCost = 0;
for (let i = 1; i <= n; i++) {
  const root = find(i);
  cost[root] = Math.min(cost[root], friendCost[i - 1]);
}

for (const c of cost) {
  if (c !== 1e9) {
    minCost += c;
  }
}
console.log(minCost <= k ? minCost : 'Oh no');

 

 

코드 설명

먼저 학생의 수 n과 친구관계 수 m이 주어졌으므로,

학생을 정점, 친구관계를 간선으로 나타내면 그래프와 관련된 문제라는 것을 알 수 있습니다.

 

문제에서 '친구의 친구는 친구다'를 이용하여 가장 적은 비용으로 모든 사람과 친구가 되는 방법을 구하라고 주어집니다.

이는 친구 관계가 방향 없이 모두 연결되어 있는 그래프라는 것을 나타냅니다.

따라서 유니온-파인드 알고리즘을 사용해 구할 수 있습니다 😊

 

코드 단계별 설명

1️⃣ 입력 처리

const [n, m, k] = input[0].split(' ').map((i) => +i);
const friendCost = input[1].split(' ').map((i) => +i); 
const friendRelation = input.slice(2).map((real) => real.split(' ').map((i) => +i));

• n : 학생 수
• m : 친구 관계 수
• k : 내가 가진 돈
• friendCost : 각 학생이 친구가 되기 위해 필요한 비용 배열
• friendRelation : 친구 관계를 나타내는 배열

---

2️⃣ 유니온-파인드를 위한 초기화

const parent = Array.from({ length: n + 1 }, (_, i) => i);

• parent[i] : 학생 i의 부모(루트)를 저장하는 배열
• 처음에는 모두 자기 자신을 루트로 설정해야 합니다.

---

3️⃣ 유니온-파인드 (Union-Find) 함수 구현

make() 

const make = () => {
  for (let i = 1; i <= n; i++) {
    parent[i] = i;
  }
};

• 모든 노드(학생)의 부모를 자기 자신으로 초기화하는 함수입니다.

find() 

const find = (a) => {
  if (parent[a] === a) return a;
  return (parent[a] = find(parent[a]));
};

• find(a): 노드 a의 루트(최상위 부모)를 찾는 함수입니다.
• 경로 압축(Path Compression)을 사용하여 재귀적으로 부모를 갱신하여 최상위 부모를 찾습니다.

union()

const union = (a, b) => {
  const rootA = find(a);
  const rootB = find(b);
  if (rootA !== rootB) {
    parent[rootB] = rootA;
    return true;
  }
  return false;
};

• 두 학생 a와 b가 같은 그룹이 되도록 유니온, 즉 집합을 merge합니다.
• 두 노드의 부모를 각각 찾은 뒤, rootB의 부모를 rootA로 설정합니다. (반대로도 가능!)
• return 값은 boolean으로, 만약 찾을 수 없는 경우 false를 반환합니다.

---

4️⃣ 친구 관계 연결

make();
for (let i = 0; i < m; i++) {
  const [v, w] = friendRelation[i];
  union(v, w);
}

• make()를 호출하여 초기화 후,
• 주어진 m개의 친구 관계를 union(v, w)로 병합합니다.

---

5️⃣ 그룹별 최소 친구비 계산

const cost = Array.from({ length: n + 1 }, () => 1e9);
let minCost = 0;
for (let i = 1; i <= n; i++) {
  const root = find(i);
  cost[root] = Math.min(cost[root], friendCost[i - 1]);
}

• cost[i] : i번째 학생이 속한 그룹(루트 노드)의 최소 친구비
• 모든 학생을 순회하면서 find(i)를 통해 루트 노드를 찾고,
• 각 루트 그룹에서 가장 최소인 친구비를 cost[root]에 저장하여 갱신합니다.

---

6️⃣ 최소 비용 계산 및 정답 출력

for (const c of cost) {
  if (c !== 1e9) {
    minCost += c;
  }
}
console.log(minCost <= k ? minCost : 'Oh no');

• cost 배열에서 초기에 주어진 무한대가 아닌 값만 더하여 총 최소 비용 minCost를 구합니다.
• k 이하라면 최소 비용을 출력하고, 아니라면 Oh, no를 출력합니다.

 

 

---