[Python] 백준 1043 거짓말

1. 문제 - 백준 1043 거짓말

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

 

💡알고리즘 - 집합, 유니온-파인드 알고리즘

• 문제의 조건을 정리해보면,
  이야기의 진실을 아는 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다.
  당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 지민이는 이런 일을 모두 피해야 한다.
• 요약하면 이야기의 진실을 아는 사람, 이야기의 진실을 아는 사람에게 들은 사람이 없는 파티에서만 과장된 이야기를 할 수 없다.
  => 파티의 사람들을 입력받을 때, 파티 인원들끼리 같은 집합으로 만들어(유니온 연산) 각 파티의 구성원 중 1명이라도 진실을 아는 사람의 집합의 구성원인지를 비교하면 된다.
  => 서로 같은 집합에 속하는지의 여부를 알려면, 루트 노드(=부모 노드)를 비교하면 된다. (파인드 연산)

✅ 풀이

n, m = map(int, input().split())
know_persons = list(map(int, input().split()))
parties = []
for _ in range(m):
  parties.append(list(map(int, input().split())))

if know_persons[0] == 0:  # 진실을 아는사람이 1명도 없는 경우, m개의 모든 파티를 갈 수 있으므로 출력 후 종료한다.
  print(m)
  exit()

parent = [i for i in range(n+1)]
def find(x):
  if parent[x] == x:
    return x

  parent[x] = find(parent[x])
  return parent[x]

def union(x, y):
  root_x = find(x)
  root_y = find(y)

  if root_x < root_y:
      parent[root_y] = root_x
  else:
      parent[root_x] = root_y

for i in range(m):
  party_persons = parties[i][1:]
  n = len(party_persons)

  for j in range(n-1):   
    # 파티를 참석한 모든 사람들에 대해 유니온 연산 실행하여 부모노드 같게해서, 같은 집합으로 만든다.
    union(party_persons[j], party_persons[j+1])

result = 0
for i in range(m):
  possible = True
  first = parties[i][1]

  for j in range(1, len(know_persons)):
    # 각 파티의 구성원 중 1명이라도 진실을 아는 사람의 집단에 속해있다면,
    # 즉 파티 구성원의 부모 노드와 진실을 아는 사람 집단의 부모 노드가 같은지를 비교하여 확인
    if find(first) == find(know_persons[j]):
      possible = False
      break

  if possible:
      result += 1

print(result)