1043

날짜 : 2023. 04. 27

사용 언어 : python

 

문제

 

 

코드

import sys

n, m = map(int, sys.stdin.readline().split())
know = set(sys.stdin.readline().split()[1:])
party = list()

for _ in range(m):  # 파티 입력
    party.append(set(sys.stdin.readline().split()[1:]))

for _ in range(m):
    for p in party:  # 각 파티별 합집합 생성
        if p & know:  # 교집합이 있는 경우(진실 아는 사람 있음)
            know = know.union(p)  # 진실 집합에 포함


res = 0
for p in party:  # 파티별로 체크
    if p & know:  # 파티 참여 인원 중 진실 아는 케이스(교집합이 있는 경우)
        continue  # 통과
    else:  # 아닌 경우
        res += 1  # 과장 가능
print(res)

 

 

풀이

- set을 활용해서 문제를 풀이한다.

- 조건에 맞게 입력받은 후 진실을 아는 집합 know를 생성한다.

- 이후 파티를 입력받으면서 해당 파티의 사람들 중에 know와 교집합이 있는지 확인한 후 교집합이 있는 경우 해당 파티의 인원을 know에 포함시킨다.(union)

- 첫 for문을 돌린 후 다시 파티를 돌리면서 최종 진실 리스트(know)를 토대로 교집합을 체크하면서, 전부 포함되지 않는 케이스를 취합 후 출력한다.

테스트케이스7의 풀이 (중괄호 : 진실 아는 사람들의 리스트)

 

알게된 점

- 각 집합의 parent를 활용해 union-find로 문제를 풀이하려 했지만 마지막 4, 5번째 테스트케이스에서 계속 틀린 답이 나와 다른 풀이를 참고했다.

- set을 활용해 교집합을 통해 진실여부를 확인할 수 있었고, 해당 element를 편입하는 방식으로 최신화가 가능했다.

- 최근 문제를 풀면서 라이브러리나 기본문법에서 많은 부족함을 느끼는 것 같은데 공부하면서 부족했던 부분을 채워나갈 필요가 있는 것 같다.

- 추가로 다시 공부하면서 union-find를 활용해 풀어보아야겠다.

 

 

참고 사이트

- https://ku-hug.tistory.com/148

[Python/파이썬] 백준 1043번: 거짓말