파이썬 백준 1043번 : 거짓말

문제

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

 

 

🤥풀이

알고리즘

연결요소를 탐색이라고 생각하여 바로 BFS를 떠올렸다. 

자료구조

people Graph 표현방식에 인접 리스트를 사용하였다. 

visited와 party_people는 이후 issubset을 이용하기 위해 set으로 구현하였다. 

 

1. 파티에 함께 참여하는 사람들을 인접 리스트로 표현한다.

# 예제 입력 1의 결과
people= [[], [2], [1, 3, 4], [2, 4], [2, 3]]

2. 진실을 알고있는 사람들과, 그와 연결되어있는모든 사람들을 방문처리한다.

 

3. 방문처리된 사람들이 존재하지 않는 파티만 count한다.  

import sys
from collections import deque

def BFS(target): 
    queue=deque()
    queue.append(target)
    while(queue):
        k=queue.pop()
        visited.add(k)
        for kk in people[k]:
            if kk not in visited:
                queue.append(kk)

N,M=map(int,sys.stdin.readline().split())
num_know,*known_people=map(int,sys.stdin.readline().split())
party_people=[]
visited=set()
people=[[] for _ in range(N+1)] #모든 사람들을 나타낸 인접 리스트
for _ in range(M):
    num_party_people,*temp_party_people=map(int,sys.stdin.readline().split())
    for i in temp_party_people: #people만들기
        for j in temp_party_people:
            if i!=j:
                people[i].append(j)
    party_people.append(set(temp_party_people))


for know in known_people: # 진실을 알고 있는사람과 연결되어있는모든 사람을 방문처리함 
    if know not in visited:
        BFS(know)

cnt=0
for party in party_people:
    if not party.issubset(visited): #방문처리된사람으로 이루어지지 않은 파티의 경우 
        cnt+=1 #cnt 증가

print(cnt)