[백준] 1043_거짓말 (Python)

1043_거짓말 (Python)

0. 출처

• 유형 : 유니온 파인드 (gold 4)
• 링크 : 1043번: 거짓말

1. 기록

• 22/07/06 (수)

2. 풀이

(1) 아이디어, 시간복잡도, 자료구조

1. 아이디어
>>
>>

2. 시간복잡도
>>

3. 자료구조
>>

(2) 예제 입력, 예제 출력

- 예제 입력 1 -
사람의 수 / 파티의 수
4 3

진실을 아는 사람의 수 / 그 번호
0

각 파티마다 오는 사람의 수 / 그 번호
2 1 2
1 3
3 2 3 4

- 예제 출력 1 -
3

- 예제 입력 2 -
4 1

진실을 아는 사람의 수 / 그 번호
1 1

각 파티마다 오는 사람의 수 / 그 번호
4 1 2 3 4

- 예제 출력 2 -
0

- 예제 입력 3 -
4 1
0
4 1 2 3 4

- 예제 출력 3 -
1

- 예제 입력 4 -
각 파티마다 오는 사람의 수 / 그 번호
4 5

진실을 아는 사람의 수 / 그 번호
1 1

각 파티마다 오는 사람의 수 / 그 번호
1 1
1 2
1 3
1 4
2 4 1

- 예제 출력 4 -
2

- 예제 입력 5 -
사람의 수 / 파티의 수
10 9
4 1 2 3 4

각 파티마다 오는 사람의 수 / 그 번호
2 1 5
2 2 6
1 7
1 8
2 7 8
1 9
1 10
2 3 10
1 4

- 예제 출력 5 -
4

- 예제 입력 6 -
8 5
3 1 2 7
2 3 4
1 5
2 5 6
2 6 8
1 8

- 예제 출력 6 -
5

- 반례 1 -
4 5
1 1
1 1
1 2
1 3
2 4 2
2 4 1

- 출력 -
1

(3) 코드

import sys

def input():
    return sys.stdin.readline().rstrip()

# fixme - 사람의 수 / 파티의 수
n, m = map(int, input().split())

# fixme - 진실을 아는 사람의 수 / 그 번호
temp1 = list(map(int, input().split()))

# 진실을 아는 사람이 있는 경우
if len(temp1[1:]) >= 1:
    set_temp = set(temp1[1:])

# 진실을 아는 사람이 없는 경우
else:
    set_temp = {}

cnt = 0

# fixme - parties 에는 각 파티와 구성원을 담아줄 것 입니다.
parties = []

for _ in range(m):

    # fixme - temp2 에는 문제에서 주어지는 파티의 구성원을 담아줍니다.
    temp2 = list(map(int, input().split()))
    parties.append(temp2)
    flag = False
    for t in temp2[1:]:
        # fixme - 파티원 중 1명이라도 set_temp 에 이미 있는 경우
        if t in set_temp:
            flag = True

        # fixme - 해당 파티에 있는 모든 사람들을 set_temp 에 추가해준다. (진실을 아는 사람이 됩니다.)
        if flag == True:
            for t2 in temp2[1:]:
                set_temp.add(t2)

for party in parties:
    flag = False

    for p in party[1:]:
        # fixme - 파티원 중 1명이라도 set_temp 에 이미 있는 경우
        if p in set_temp:
            flag = True

    # fixme - 파티원 중 아무도 진실을 알지 못하는 경우
    if flag == False:
        cnt += 1

print(cnt)

(4) 정리

이 문제에서 좀 더 설명이 추가한 부분은 시간 순서와 상관없이 이전 파티였어도 이후에 진실을 아는 구성원과 파티를 이룬적이 있는 구성원은 해당 구성원이 속했던 전에 파티에 있던 사람도 진실을 알게끔 처리해주어야 합니다. (마치 타임머신을 타고오듯?)
그래서 해당 구성원들을 모두 연결 시켜주어야 하며 이때 사용한 개념이 유니온 파인드입니다.
해당 알고리즘을 몰라 동빈나님 영상을 참고하고 구현하였습니다.

(5) 참고

유니온 파인트 개념 익히기