백준 1043 거짓말

문제

👀 문제 사이트 : https://www.acmicpc.net/problem/1043

이 문제는 진실을 아는 사람들에게는 거짓말을 하면 안되고, 한 사람에게 거짓말과 진실을 말하면 안되는 조건이 있을 때, 파티에 온 사람들에게 거짓말을 할 수 있는 최대 경우의 수를 구하는 문제이다.

풀이

난이도 : GOLD IV

1) 처음 진실을 아는 사람들을 같은 집합으로 생각하고, 한 번에 파티에서 같이 오는 사람들을 모두 같은 집합으로 만들어주어 분리 집합(Union-Find)을 만들어주었다.
2) 분리 집합을 만들어준 후, 다시 파티를 탐색하며 진실이 아는 사람들의 집합에 해당 파티가 포함되지 않는 경우에 그 파티에서는 거짓말을 할 수 있다는 것으로 판단하였다.
3) 1~2의 과정을 거쳐 거짓말을 할 수 있는 파티의 수를 세어 정답을 출력하였다.

코드

# 분리 집합 (union, find)
def find_parent(parent, x):
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = parent[a]
    else:
        parent[a] = parent[b]

n, m = map(int, input().split())
parent = [i for i in range(n + 1)]

# 진실을 알고 있는 사람들은 같은 집합으로 설정
tmp = list(map(int, input().split()))
for i in range(2, len(tmp)):
    if find_parent(parent, tmp[1]) != find_parent(parent, tmp[i]):
        union_parent(parent, tmp[1], tmp[i])

# 파티 입력
parties = []
for _ in range(m):
    party = list(map(int, input().split()))

    # 파티에 같이 온 사람들은 같은 집합으로 설정
    for i in range(2, len(party)):
        if find_parent(parent, party[1]) != find_parent(parent, party[i]):
            union_parent(parent, party[1], party[i])
    parties.append(party)

# 진실을 알고 있는 사람이 없으면 정답 출력
if tmp[0] == 0:
    print(m)
    exit(0)

# 진실 집합의 부모
truth_p = find_parent(parent, tmp[1])

# 파티 탐색하며 진실 집합에 속해있지 않으면 정답으로 카운트
result = 0
for party in parties:
    if truth_p != find_parent(parent, party[1]):
        result += 1

print(result)