🔴 문제
🟡 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] = inputs[0].split(' ').map(Number);
const p = Array.from({ length: n }).map((_, idx) => idx);
const knowingPeople = inputs[1]
.split(' ')
.slice(1)
.map((it) => Number(it) - 1);
const parties = inputs.slice(2).map((it) =>
it
.split(' ')
.slice(1)
.map((it) => Number(it) - 1)
);
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 (let i = 1; i < knowingPeople.length; i++) {
union(knowingPeople[0], knowingPeople[i]);
}
for (const party of parties) {
for (let i = 1; i < party.length; i++) {
union(party[0], party[i]);
}
}
let ans = m;
const target = knowingPeople.length > 0 ? find(knowingPeople[0]) : -1;
for (const party of parties) {
for (const person of party) {
if (find(person) === target) {
ans -= 1;
break;
}
}
}
console.log(ans);🟢 풀이
⏰ 소요한 시간 : -
이 문제는 비밀을 알고있는 사람들을 하나의 집합으로 여긴 뒤 파티에 참여한 사람중 비밀을 알고있는 사람이 있다면 해당 파티에 참여한 사람들을 모두 하나의 집합으로 바꿔주는 유니온 파인드로 풀이할 수 있다.
입력 첫줄로 n과 m을 받고 parent 배열 p를 만들어 초기화 해준다.
비밀을 알고 있는 사람들의 정보를 입력의 두 번째 요소로부터 문자열로 받아와 split 해 배열로 변환해준 뒤, 비밀을 알고있는 사람인 몇명인지에 대한 정보는 제거하기 위해 slice를 적용시켜주었다. 그리고 입력은 1번부터 n번까지의 사람정보로 주어지므로 1을 빼서 0부터 시작할 수 있도로 해주었다.
파티 정보는 입력의 세 번째 요소부터 쭉 주어지기 때문에 slice(2)를 사용하여 배열을 잘라주었고 각 요소 내부에서도 위와 동일하게 파티에 참가한 사람이 몇명인지에 대한 정보를 제거한 뒤 1을 빼주었다.
유니온 파인드를 수행할 함수를 만들어준 뒤 비밀을 알고있는 사람들을 하나의 집합으로 수정해준다. 비밀을 알고있는 사람들을 순회하며 비밀을 알고있는 사람중 첫번째(0번째) 요소와 union연산을 진행한다. 그리고 아까 입력받았던 파티들의 정보를 순회하면서, 같은 파티에 참여한 사람들을 같은 집합으로 묶어주는 union 연산을 수행한다.
마지막으로 파티를 순회하면서 하나의 파티에 비밀을 알고있는 사람이 있는지 확인해줘야 한다. 비밀을 알고 있는 사람배열의 길이가 0 이상이면 그 중 첫 요소의 부모를 찾아 target에 할당한다. 첫 요소가 아니어도 된다. 어차피 비밀을 알고 있는 사람들의 부모는 모두 동일하다.
하나의 파티 내의 사람의 부모가, target과 동일하다면 해당 사람은 비밀을 알고있으므로 ans값을 1 감소 시키고 그 파티를 종료하면 된다.
splice와 split를 잘 외워놓지 않아 사용하지 않았던 메서드였는데 이참에 익힌 것 같아 좋다.
🔵 Ref
