문제
풀이
문제 이해
우선 문제 이해를 해보자면 지민이는 각각의 파티마다 거짓말 혹은 진실을 말해야 하는데, 파티에 진실을 알고 있는 사람이 있을 경우 진실을 말하고, 진실을 알고 있는 사람이 없을 경우엔 거짓말을 한다.
그리고 우리는 지민이가 최대 몇 개의 파티에서 거짓말을 할 수 있는지 알아내야 한다.
입력값이 아래와 같이 주어졌다고 가정해보자.
4 5
1 1 // 진실을 아는 사람 1
1 1 // 파티 1
1 2 // 파티 2
1 3 // 파티 3
1 4 // 파티 4
2 4 1 // 파티 5이 경우 처음에 진실을 알고 있는 사람은 1번 밖에 없으므로
파티 2,3,4 에서 거짓말을 해도 되는것 처럼 보이지만 만약 파티 2,3,4 에서 거짓말을 했다면 파티 5에서 1번이 있기 때문에 4번도 진실을 듣게 되고, 지민이는 거짓말쟁이가 된다.
따라서 파티 4에서도 진실을 말해야 거짓말쟁이가 되지 않는다.
정리해보자면 진실을 아는 사람이 파티에 포함되어 있을 경우 해당 파티에 있는 모든 사람이 진실을 듣는 것이기 때문에 해당 파티에 있는 모든 사람들이 진실을 아는 사람이 되는 것이다.
시행 착오
처음엔 반복문으로 모든 파티를 순회하며 진실을 아는 사람이 포함된 파티일 경우 해당 파티에 있는 모든 사람들의 번호를 Set() 으로 만든 변수에 저장하여, 진실을 아는 사람들의 목록을 만들고, 다시 한 번 파티를 순회하며 파티에 진실을 아는 사람이 있을 경우 거짓말을 하지 않고, 진실을 아는 사람이 없을 경우엔 거짓말을 하는 방식으로 접근했다.
코드
const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [N, M] = input[0].split(' ').map(Number);
const [peopleCount, ...peopleKnowTruth] = input[1].split(' ').map(Number);
const party = input.slice(2).map((e) => e.split(' ').map(Number));
const truth = new Set(peopleKnowTruth);
let answer = 0;
// 진실을 아는 사람의 목록을 truth 변수에 저장함
for (let i = 0; i < M; i++) {
for (let j = 1; j <= party[i][0]; j++) {
if (truth.has(party[i][j])) {
party[i].slice(1).forEach((e) => truth.add(e));
break;
}
}
}
// truth 변수에 있는 번호가 포함되어 있을 경우에는 거짓말 X
// 아닐 경우에는 거짓말 O
for (let i = 0; i < M; i++) {
let known = false;
for (let j = 1; j <= party[i][0]; j++) {
if (truth.has(party[i][j])) {
known = true;
break;
}
}
if (!known) answer++;
}
console.log(answer);반례
input
5 4
1 5
2 1 2
2 2 3
2 3 4
2 4 5
ans
0
wrong output
2이 경우 5번이 진실을 알고 5->4->3->2->1 이렇게 전부 엮여있기 때문에 모든 파티에서 진실을 말해야 된다. 하지만 내가 작성한 코드에서는 파티를 앞에서 부터 순차적으로 순회하며 truth 변수를 갱신하기 때문에 truth 변수에는 [5, 4] 만 저장되고 따라서 첫 번째 파티와 두 번재 파티에서 거짓말을 하기 때문에 잘못된 출력이 나온다.
수정된 코드
따라서 파티를 역순으로도 순회해주며 truth 변수를 갱신해주었다.
const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [N, M] = input[0].split(' ').map(Number);
const [peopleCount, ...peopleKnowTruth] = input[1].split(' ').map(Number);
const party = input.slice(2).map((e) => e.split(' ').map(Number));
const truth = new Set(peopleKnowTruth);
let answer = 0;
// 첫 번째 파티에서 부터 마지막 파티까지 진실을 알고 있는 사람의 집합을 구한다.
for (let i = 0; i < M; i++) {
for (let j = 1; j <= party[i][0]; j++) {
if (truth.has(party[i][j])) {
party[i].slice(1).forEach((e) => truth.add(e));
break;
}
}
}
// 마지막 파티에서 부터 첫번째 파티까지 진실을 알고 있는 사람의 집합을 구한다.
for (let i = M - 1; i >= 0; i--) {
for (let j = 1; j <= party[i][0]; j++) {
if (truth.has(party[i][j])) {
party[i].slice(1).forEach((e) => truth.add(e));
break;
}
}
}
// 진실을 알고 있는 사람이 포함된 파티라면 카운트하지 않고, 포함되어있지 않다면 카운트한다.
for (let i = 0; i < M; i++) {
let known = false;
for (let j = 1; j <= party[i][0]; j++) {
if (truth.has(party[i][j])) {
known = true;
break;
}
}
if (!known) answer++;
}
console.log(answer);반례
input
6 5
1 4
2 1 2
2 2 3
2 3 4
2 2 5
2 5 6
ans
0
wrong output
1첫 번째 반례는 해결되었지만 위 반례에서 또다시 오답이 출력된다. 이 경우에도 모두 진실을 알도록 엮여있기 때문에 모든 파티에서 진실을 말해야 한다.
하지만 코드에는 파티를 앞에서부터 순차적으로 탐색했을 경우에 truth 변수가 [4, 3]으로 갱신되고, 역순으로 한번 더 탐색했을 때 [4, 3, 2, 1] 로 갱신된다.
따라서 4번,3번,2번,1번이 포함된 1~4번째 파티에서는 진실을 말하겠지만 마지막 파티에서 거짓말을 하게 되므로 오답이 출력된다.
또다시 첫번째 파티에서부터 마지막 파티까지 순회하는 반복문을 추가하여 truth 변수를 또다시 갱신해주면 위 반례는 풀 수 있겠지만 아래 반례처럼 데이터가 추가되면 또다시 오답이 출력된다.
input
6 5
1 4
2 7 8
2 1 2
2 2 3
2 3 4
2 2 5
2 5 6
2 6 7
ans
0
wrong output
1따라서 이렇게 해결할 수 있는 문제가 아니므로 다른 방식을 찾아봐야 한다.
해결
해당 문제는 유니온 파인드를 사용해서 푸는 문제였다.
같은 파티에 있는 번호들 끼리 같은 루트 노드를 가리키도록 union()함수를 실행시켜주고, 각각의 파티에 한 사람을 임의로 골라서(party[i][1]) 그 사람이 진실을 아는 사람(peopleKnowTruth[j])과 엮여있다면(if (find(peopleKnowTruth[j]) === find(party[i][1]))) 해당 파티에서는 거짓말을 하면 안되므로 처음에 파티의 개수(M)로 초기화한 answer변수를 1 감소시킨다.
코드
const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const [N, M] = input[0].split(' ').map(Number);
const [peopleCount, ...peopleKnowTruth] = input[1].split(' ').map(Number);
const party = input.slice(2).map((e) => e.split(' ').map(Number));
const parent = Array(N + 1);
for (let i = 0; i <= N; i++) {
parent[i] = i;
}
let answer = M;
// 같은 파티에 있는 사람들의 번호끼리 집합으로 연결한다.
for (let i = 0; i < M; i++) {
for (j = 1; j < party[i][0]; j++) {
union(party[i][j], party[i][j + 1]);
}
}
// 진실을 아는 사람이 파티에 포함되어 있을 경우 해당 파티에서는 거짓말을 하지 못하므로 카운트를 1 감소시킨다.
for (let i = 0; i < M; i++) {
for (j = 0; j < peopleCount; j++) {
if (find(peopleKnowTruth[j]) === find(party[i][1])) {
answer--;
break;
}
}
}
console.log(answer);
function union(a, b) {
a = find(a);
b = find(b);
if (a < b) parent[b] = a;
else parent[a] = b;
}
function find(x) {
if (parent[x] !== x) parent[x] = find(parent[x]);
return parent[x];
}
참고
