[Python] 백준 1043번 - 거짓말

문제

• 백준 1043번

최종 코드

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
truth = list(map(int, input().split()))
people = [i for i in range(n + 1)]
parties = []


def union(a, b):
    if people[a] != a:
        a = find(a)
    if people[b] != b:
        b = find(b)

    if a != b:
        people[b] = a


def find(a):
    if people[a] == a:
        return a

    root = find(people[a])
    people[a] = root
    return root


if truth[0] == 0:
    print(m)
    exit(0)

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

    for i in range(1, len(party)):
        union(party[0], party[i])

result = 0
for i in range(m):
    root_party = find(parties[i][0])

    has_truth = False
    for j in range(1, len(truth)):
        root_truth = find(truth[j])

        if root_truth == root_party:
            has_truth = True
            break

    if not has_truth:
        result += 1

print(result)

 

풀이 과정

---

• 첫째 줄에 사람 수 N과 파티의 수 M이 주어지며, 둘째 줄에서는 진실을 아는 사람 수와 번호가 주어진다
  • 이때 문제의 예제 입력 1과 같이 진실을 아는 사람 수가 0일 경우 굳이 다음 입력을 받아 처리할 필요가 없으므로, 최종 코드의 29번째 줄과 같이 파티의 수(M)를 출력하고 프로그램을 종료하도록 했다
• 지민이가 파티에서 과장된 이야기를 할 수 있으려면, 해당 파티의 참석자 중에 진실을 알거나 진실을 아는 사람이 있는 파티에 참석한 적 있는 사람이 있으면 안된다
  • 따라서 union-find 알고리즘에서 union 연산을 이용하여 다른 파티에 있어도, 참석자가 겹치는 파티들을 첫 번째 참석자를 기준으로 하나의 그룹으로 묶었다
  • 이후 find 연산을 이용하여 각 파티마다 첫 번째 참석자의 그룹과 진실을 아는 사람들의 그룹을 알아내었고, 이를 비교하여 같은 그룹일 경우 has_truth 플래그를 True로 하여 해당 플래그가 False일 경우에만 거짓말을 할 수 있는 파티로 계산하였다
• 다행히도 한 번에 정답처리 되어 따로 반례를 찾지 않은 문제였다!

틀린 부분 또는 궁금한 점은 댓글로 남겨주세요! 항상 환영합니다!