🔴 문제
🟡 Sol
const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'Wiki\\input.txt';
const inputs = fs.readFileSync(path).toString().trim().split('\n');
const [n, m, k] = inputs[0].split(' ').map(Number);
const A = inputs[1].split(' ').map(Number);
const infos = inputs.slice(2);
const p = Array.from({ length: n }).map((_, idx) => Number(idx));
const find = (a) => {
if (p[a] !== a) p[a] = find(p[a]);
return p[a];
};
const union = (a, b) => {
const pa = find(a);
const pb = find(b);
p[pb] = pa;
};
for (const info of infos) {
const [v, w] = info.split(' ').map((it) => Number(it) - 1);
union(v, w);
}
for (let i = 0; i < n; i++) {
p[i] = find(i);
}
let sum = 0;
for (const target of new Set(p)) {
let min = 10001;
for (let i = 0; i < n; i++) {
if (p[i] === target && min > A[i]) min = A[i];
}
sum += min;
}
if (sum > k) console.log('Oh no');
else console.log(sum);🟢 풀이
⏰ 소요한 시간 : 40분
친구의 친구는 친구다! -> 두 친구 무리를 합쳐서 하나의 친구 무리로 만든다 -> 유니온 파인드를 사용한다
위와 같은 사고 흐름으로 유니온 파인드를 사용해주면 된다.
첫 줄에서 학생수 n과 친구관계수 m, 가진 돈 k를 숫자로 매핑해 입력받는다.
두 번째 줄은 친구비 A배열이다. 숫자로 매핑해 입력받았다.
세 번째 줄부터는 친구관계 정보를 입력받아야 하므로 slice 사용해서 입력받아 줬다.
대표 집합을 나타내는 부모 배열 p도 만들어 주었다.
그 후 유니온 파인드 함수를 만들고 infos 배열을 순회하면서 두 학생을 하나의 집합으로 합쳐주는 union 연산을 수행한다.
모든 학생의 정보를 순회하며 union연산을 마치고 난 후, 다시 한번 부모배열을 순회하면서 각 요소가 자신이 속한 집합의 대표 요소 값을 가질 수 있도록 한다.
이제 친구비를 구해야 하는데, 방금 p배열을 순회하면서 대표 요소 값만 가질 수 있도록 했기 때문에 p배열을 set으로 변경해 중복을 제거하여 반복한다. 그 안에서 p배열을 순회하면서 각 집합의 대표값인 target의 집합에 속한 요소들을 찾아 친구비의 최소값을 구해준다.
최소값을 구했으면 해당 값을 sum에 누적시켜 총 친구비를 구해준다.
마지막에 친구비가 내가 가지고 있는 돈 k보다 크면 Oh no를 출력(대소문자 주의) 아니면 친구비를 출력한다.
이 문제의 포인트는 친구 정보를 순회하며 유니온 연산을 마친 후에 한 번 더 유니온 연산을 하여 부모배열의 각 요소를 대표값으로 업데이트 해줘야한다는 것이다.
🔵 Ref
