[백준/G4] 1043 거짓말

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

시간복잡도

O(N**2)과 유사

• 진실을 아는 사람들을 묶는 과정 : O(N)
• 각 파티 참여자들을 묶는 과정 : O(M * log N)
• 각 파티를 탐색, 거짓말 할 수 없는 파티를 판단 : O(M N α(N))

+) α(N) : 역 아커만 함수의 값으로, 상수값과 유사하다고 함(어떤 N이 들어오든 5보다 작다)

풀이

마주치는 파티 참여자들을 하나로 묶는 방식이 필요했으므로 그래프 형태를 생각해야 했고, Union-Find 를 활용함

1. 진실을 아는 사람들을 전부 묶고(부모를 모두 0으로)
2. 각 파티 참여자들을 순회하며 묶고(각 첫번째 파티원과 그다음 파티원을 비교함, 더 작은 값을 부모로)
3. 그다음 다시 전체 파티를 순회하며 find로 (부모값을 다시 한번 업데이트해가며) 거짓말 할 수 없는 파티를 판단한다.

3번에서 다시 부모값 업데이트가 필요한 이유는 2번에서 첫번째 파티원과 그다음 파티원을 비교하는 방식이기 때문

ex) parent가 [0,1,1,0]과 같은 상황일 경우
1(idx 1)과 1(idx 2)을 비교해서 업데이트하면 [0,1,1,0]이고,
그다음 1(idx 1)과 0(idx 3)을 비교할 경우 [0,0,1,0]이 됨
하지만 1, 2, 3 모두 같은 묶음이기 때문에 결론적으론 [0,0,0,0]이 맞는 값이다.
→ 이렇게 업데이트되지 못한 부분을 위해 마지막에 다시 find를 통해 업데이트 해야함

최종코드

function find(parent, x) {
  if (parent[x] !== x) {
    parent[x] = find(parent, parent[x]);
  }
  return parent[x];
}

function union(parent, a, b) {
  const parentA = find(parent, a);
  const parentB = find(parent, b);

  // 최대한 더 작은 값을 부모로 하며 묶음
  if (parentA <= parentB) {
    parent[parentB] = parentA;
  } else if (parentA > parentB) {
    parent[parentA] = parentB;
  }
}

function getMaxParty(N, M, know, parties) {
  let cnt = M;
  // 진실을 아는 사람이 없다면 조기 return
  if (!know[0]) return cnt;

  // parent(root)를 저장하는 배열
  const parent = Array.from({ length: N + 1 }, (_, idx) => idx);
  const knownPeople = know.slice(1);
	
  // 1. 진실을 아는 사람은 0으로 묶음(parent가 0)
  for (let person of knownPeople) {
    parent[person] = 0;
  }

  // 2. 파티에 참여한 사람들을 같은 집합에 묶이도록 함
  for (let party of parties) {
    let firstPerson = party[1];
    for (let i = 2; i < party.length; i++) {
      let comparedPerson = party[i];
      union(parent, firstPerson, comparedPerson);
    }
  }

  // 3. 파티를 탐색하며 소속된 사람의 부모의 소속(업데이트를 위해 find를 써야함)이
  // '진실을 아는 집합(0)'임을 확인한다면 해당 파티는 거짓말을 할 수 없음
  for (let party of parties) {
    for (let i = 1; i < party.length; i++) {
      let person = party[i];
      if (find(parent, person) === 0) {
        cnt -= 1;
        break;
      }
    }
  }

  return cnt;
}

// 거짓말쟁이로 판단되지 않으면서, 거짓말을 퍼뜨릴수 있는 파티 갯수 최댓값
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./1043.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const [N, M] = input[0].split(" ").map(Number);
const know = input[1].split(" ").map(Number);
const parties = input.slice(2).map((l) => l.split(" ").map(Number));

let answer = getMaxParty(N, M, know, parties);

console.log(answer);

+) union by rank 등의 방법을 통해 두 트리의 루트 노드의 rank(규모)를 비교하여 rank가 더 작은 트리가 rank가 더 큰 트리의 자식으로 병합하는 방법으로 시간복잡도를 더 줄일 수 있다고 함(tree의 depth와는 조금 다른 개념)