[알고리즘][Python] 백준 1043 거짓말 문제 풀이

문제 출처 : www.acmicpc.net/problem/1043

1043번: 거짓말

---

문제 해석 : 지민이는 이야기의 진실을 모르는 자리에서는 과장된 이야기를 하고 진실을 아는 사람이 있는 곳에서는 진실된 이야기를 한다. 이때 과장된 이야기를 할 수 있는 파티의 수를 구하는 문제이다.

 

문제 풀이 : 단순하게 진실을 아는 사람 수를 체크하면 순서관계가 얽히게 되면 정답을 도출할 수 없게 된다.

 

예를 들어

1번 파티 1, 2

2번 파티 2, 3

3번 파티 3, 4

4번 파티 4, 5

5번 파티 5. 6

 

처럼 파티가 주어지게 된다면 그 어느 곳에서도 과장된 이야기를 할 수 없다. 따라서 입력을 모두 받고 전체를 다시 체크하는 기능이 필요하다.

 

가능한 풀이 : BFS, 브루트 포스 방법으로 풀 수 있다.

---

풀이 코드

def check_group():
    global know

    for key in group:
        if len(know.intersection(set(group[key]))) != 0 and visited[key] == 0:
            possible[key] = 0
            visited[key] = 1
            know = know.union(set(group[key]))
            check_group()

N, M = map(int, input().split())

know = set(list(map(int, input().split()))[1:])

group = {}
possible = [1] * M
visited = [0] * M
for i in range(M):
    temp = list(map(int, input().split()))[1:]
    group[i] = temp

    if len(set(temp).intersection(know)) != 0:
        know = know.union(set(temp))

check_group()

print(sum(possible))

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.