[Python] 1043번 : 거짓말

 

문제 설명 3줄 요약

 

1. 지민이는 과장해서 이야기하는 것을 좋아한다.

2. 그 이야기의 진실을 아는 사람을 최대한 피해서 과장되게 이야기 하고싶다.

3. 최대 몇개의 파티에서 과장되게 이야기할 수 있을까

 

 

 

 

처음엔 문제를 굉장히 쉽게 생각하여

set로 파티 인원과 진실을 아는 사람의 중복을 제거 하는 것으로 접근하려 했으나,

진실을 아는 인원과 파티를 즐긴 사람도

곧, 진실을 알게되는 인원인 것을 고려해주지 않았다는 것을 깨달았다.

 

때문에 진실을 아는 인원을

각 파티에 참여했던 인원을 반복해서 탐색하며 갱신해주고,

최종적으로 과장되게 이야기할 수 있는 파티의 수를 카운트 해주었다.

 

 

from sys import stdin

if __name__ == "__main__":

	## 사람의 수 N, 파티의 수 M
    N, M = map(int, stdin.readline().split())
    
    ## 이야기의 진실을 아는 사람의 수와 번호
    ## 진실을 아는 사람 또 알게될 사람은 진실 리스트에 담는다.
    truth = list(map(int , stdin.readline().split()))
    
    truth_list = []
    party_list = [] # -> 전체 파티를 담는 리스트, 반복해서 탐색할 예정

    for idx in range(1,truth[0]+1):
        truth_list.append(truth[idx])
    
    for _ in range(M):
    ## 각 파티마다 오는 사람의 수와 번호
        party_num = list(map(int , stdin.readline().split()))
        
        member = []
        check = False
        for idx in range(1,party_num[0]+1):
            if party_num[idx] in truth_list:
                check = True
            member.append(party_num[idx])
        
        ## 진실을 아는 사람이 포함된 파티
        if check:
            for i in member:
                if i not in truth_list:
                    truth_list.append(i)
            check = False
        else:
            party_list.append(member)

    cnt = 0

	## 진실을 아는 인원 리스트를 갱신해주며 파티를 걸러낸다.
    while(len(truth_list) != cnt):
        check_num = truth_list[cnt]
        remove_list = []
        for idx, party in enumerate(party_list):
            if check_num in party:
                for p in party:
                    if p not in truth_list:
                        truth_list.append(p)

                remove_list.append(idx)
        
        for idx in sorted(remove_list, reverse=True):
            del party_list[idx]

        cnt += 1
    
    print(len(party_list))

 

구현하는데는 큰 어려움이 없었지만,

곧 알게될 사람인지를 고려해주는 부분을 생각해내는데 시간이 걸렸다.

그 부분을 파악한다면,

쉽게 해결 완료!

 

끝!