[BAEJOON] 1043 거짓말

거짓말

문제 요약

• 알고리즘 분류: 정렬, 재귀
• 난이도: Gold4
• 문제내용:
  • 사람수 N, 파티수 M 있다.
  • 기존에 진실을 알수 있는 사람의 수와 번호가 있다.
  • 진실을 알 수 있는 사람이랑 파티에 있는 경우 다른 사람이 알수 있어서 과장된 이야기를 할수없다.
  • 최대한 피해서 과장된 이야기 할수 있는 파티 개수를 구해라
• 사이트 주소: https://www.acmicpc.net/problem/1043

1043번: 거짓말

 

문제풀이  

1. 알고있는 사람을 set 구조를 선언한다.
2. 파티에 참여하는 사람도 set 구조로 선언한다. 그리고 아는 사람없는 파티에 대한 정보도 저장할 리스트도 선언한다.
3. 처음에 파티 참여하는 사람과 알고 있는 사람 교집합($)에서 사람이 있는 경우 파티에 참여 하는 사람과 알고 있는 사람 합집합 한다. 아는 사람이 없는 파티에 저장한다.
4.  아는 사람 없는 파티 수 많큼 루프를 돌고 그 다음 파티 반복문 돌려서 3번 을 반복한다.
5. 파티에서 과장해도 문제 없는 파티수를 구한다.

Code

Python

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

real_people = set(map(int, input().split()[1:]))

count = 0
parties = []

for _ in range(M):
    party = set(map(int, input().split()[1:]))
    if party & real_people:
        real_people = real_people.union(party)
    parties.append(party)

for _ in range(len(parties)):
    for party in parties:
        if party & real_people:
            real_people = real_people.union(party)

for party in parties:
    count += 0 if party & real_people else 1

print(count)

유니온 파인드

import sys
input = sys.stdin.readline

def union(x, y):
    x = find(x)
    y = find(y)
    if x < y:
        parents[y] = x
    else:
        parents[x] = y

def find(x):
    if x == parents[x]:
        return x
    return find(parents[x])

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

for i in list(map(int, input().split()[1::])):
    parents[i] = 0

parties = []
for _ in range(m):
    people = list(map(int, input().split()[1:]))
    parties.append(people)
    if len(people) > 1:
        for i in range(1, len(people)):
            union(people[i-1], people[i])

count = 0
for party in parties:
    for person in party:
        if find(parents[person]) == 0:
            break
    else:
        count += 1

print(count)