[백준/Python] 1043번_거짓말(그래프 탐색)

📌문제 유형

자료구조, 그래프 이론, 그래프 탐색, 분리 집합 (골드 4)

 

📌문제

1043번: 거짓말

 

📌나의 문제풀이

- person : 사람별 참석한 파티, party : 파티에 참석한 사람

- DFS 활용해서 사람 -> 파티 순으로 순회

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

party = [[]]    # 파티에 참석한 사람
person = [[] for _ in range(n+1)]   # 사람별 참석한 파티
for i in range(m):
    go_party = list(map(int,input().split()))
    party.append(go_party[1:])
    for per in go_party[1:]:
        person[per].append(i+1)

def search_person(x):
    if x in visited_person:
        return
    
    visited_person.append(x)
    
    for num in person[x]:
        if num not in visited_party:
            visited_party.append(num)
            search_party(num)


def search_party(y):
    for p in party[y]:
        if p not in visited_person:
            search_person(p)

visited_party = []
visited_person = []

for check_p in truth[1:]:
    search_person(check_p)

print(m - len(set(visited_party)))

 

📌다른사람의 문제풀이

- 교집합, 합집합으로 풀기

https://ku-hug.tistory.com/148

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
knowList = set(input().split()[1:])
parties = []

for _ in range(m):
    parties.append(set(input().split()[1:]))

for _ in range(m):
    for party in parties:
        if party & knowList:
            knowList = knowList.union(party)

cnt = 0
for party in parties:
    if party & knowList:
        continue
    cnt += 1

print(cnt)

 

 

📌리뷰

겹치는 사람만 제거하면 됨 -> 교집합, 합집합 이용