[Baekjoon] 백준 1043 거짓말 Python

https://www.acmicpc.net/problem/1043

 

❗풀이 방법

• 파티의 입력 순서에 상관없이 같이 참석했다는 것을 기준으로 그래프 생성
• 알고 있는 사람을 기준으로 dfs 실행해서 비밀을 아는 사람 체크
• 각 파티에서 비밀을 아는 사람이 없어야 결과+1

 

 

❗코드

import sys
input = sys.stdin.readline

cnt = 0

n, m = map(int, input().split())

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

graph = [[] for _ in range(n+1)]
visited = [0 for _ in range(n+1)]

party = []



def dfs(v):
    visited[v] = 1

    for i in graph[v]:
        if not visited[i]:
            dfs(i)




# 그래프 세팅
for _ in range(m):
    people = list(map(int, input().split()))[1:]
    # print(f"people: {people}")

    party.append(people)

    if len(people) == 1:
        continue

    for i in range(0, len(people)):
        for j in range(0, len(people)):
            if i == j:
                continue
            graph[people[i]].append(people[j])
            graph[people[j]].append(people[i])
            
for row in graph:
    row = list(set(row))



# 거짓말을 알게 됐는지 여부 판단
for i in known:
    if not visited[i]:
        dfs(i)


# 몇개의 파티에 갈 수 있는지
for p in party:
    flag = True
    for e in p:
        if visited[e]:
            flag = False
    if flag:
        cnt += 1

print(cnt)