[백준] #1043 Python

백준 1043번 파이썬
https://www.acmicpc.net/problem/1043

아이디어

진실을 아는 사람이 파티 구성원 중에 있는지 없는지만 확인하면 됨 -> 배열 안의 원소 순서와는 상관없음 -> 집합 쓰자!

집합의 시간복잡도
https://dev.plusblog.co.kr/42
배열을 돌 때 순서만 상관없으면 집합을 쓰는게 유용한 것 같다.

• parties(파티 구성원들)와 truth(진실을 아는 구성원들)의 이중 for문을 돌며 진실을 아는 사람이 파티에 있을 경우, 해당 파티와 진실팟을 합집합으로 합쳐 준다.
• '진실을 아는 사람이 파티에 있을 경우'라는 조건에 의해 진실팟 규모가 점점 커질테니, 전체 파티를 다 돌 때 ans값이 갱신이 안될 때까지 반복문을 돌아야 한다. -> answer(이전 값), ans(최신 값) 같은지 비교

다른 풀이(BFS)

• 파티를 돌면서 진실을 아는 사람들이 포함돼 있는지 확인하고, 만약 있다면 나머지 사람들을 queue에 넣어준다.
• 중복은 visited 배열을 써서 걸러준다.

전체코드

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
truth = list(map(int, input().split()))
parties = []
for i in range(M):
    attendees = list(map(int, input().split()))
    parties.append(set(attendees[1:]))

if truth[0] == 0:
    print(len(parties))
else:
    truth = set(truth[1:])
    ans = len(parties)
    while True:
        answer = ans
        for i in parties:
            if i:
                for s in truth:
                    if s in i:
                        truth = truth | i
                        i.clear()
                        ans -= 1
                        break
                    else:
                        pass

        if answer == ans: #파티 순회해도 값이 바뀌지 않는다 -> 끝내도 됨
            break
        else: #파티 순회하니까 값이 바뀐다 -> 값 갱신
            continue
        
    print(answer)