[백준/BOJ] - 1043번 python 풀이 - set

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

1043번: 거짓말

---

이 문제를 처음 보고 "그래프 탐색으로 하면 될 거 같은데..?"란 생각이 들었다.

하지만 그래프를 어떤 기준으로 정렬할지에 대한 해답이 나오지 않아 직관적으로 접근했다.

기본적으로 진실을 알고있는 집합이 주어진다.

진실을 알고 있는 집합의 원소를 파티 구성원으로 가지고 있는 파티 집합을 구해야 한다.

그렇기에 테스트 케이스를 보고 윗줄부터 아랫줄을 훑으며 겹치는 파티들과 진실의 집합을 합치면 되겠다는

생각이 들었다. - union.

union 메서드나 '|' 연산을 사용하면 합집합이 구해지기 때문에 겹치는 원소들을 중복으로 지니지 않고 하나만

갖게 할 수 있다.

테케 별로 다르지만, 어떤 테케는 1번만 위아래로 훑고, 진실 집합을 구하면 해결되는 반면, 어떤 테케는 2번

이상 시도해야 정답을 구할 수 있게 된다는 것을 깨달았다.

 

WHY?

 

예시로

 

20 5
1  1
14 13
13 12
12 11
11 10
1  10

 

이런 인풋에 대해 생각해보자.

맨 처음 진실 집합은 {1}이고, 마지막 줄 1 10 을 발견해야 비로소 합집합 연산을 수행한다.

→ {1, 10}

 

그 다음 진실 집합은 {1,10}이고. 막줄에서 두번째줄 11 10을 발견하여 합집합 연산을 수행한다.

→ {1,10,11}

.

.

.

.

최종적으로 5번의 cycle을 돌아

진실집합은 {1,10,11,12,13,14}로 마무리 된다.

즉, 파티의 수만큼 반복해줘야 비로소 결과가 나온다는 의미.

 

매 사이클마다 겹치는 원소 하나를 발견하는 순간, 예외가 발생할 여지가 있어 한번 더 반복을 해주는 메커니즘인 것이다.

---

import sys
input = sys.stdin.readline
h, p  = map(int, input().split()) #사람, 파티
T = set(input().split()[1:])
arr = []
cnt = 0

for _ in range(p):
    arr.append(set(input().split()[1:]))

for i in range(p):
    for party in arr: # T와 party 비교    
        if party & T:#겹치는게 있으면
            T = party | T

for party in arr: # T와 party 비교    
    if not party & T:#겹치는게 없으면
        cnt += 1
print(cnt)