백준 1043번(거짓말) - python

접근

1. 진실을 아는 사람이 파티에 참여하면 거짓을 말하지 못한다.

2. 또다른 파티에서는 과장된 이야기를 들었을 때도 거짓말쟁이로 알려지게 된다.

 

진실을 아는 사람 그룹을 만들고 진실을 아는 사람이 파티에 있을때

bfs를 이용해 연관되어있는 사람을 모두 진실을 아는 사람 그룹에 넣는다.

그 후 해당 그룹에 인원들이 모두 없는 파티만 세어준다. 

 

ex)

5 4

1 1

2 5 2

2 2 3

2 3 1

마지막에 1번이 있지만 1번이 진실을 알아 3번도 진실을 알게되고

2번도 3번이 알아서 진실을 알게되고 결국 5번도 진실을 알게된다.

따라서 마지막 1번이 발견했을때 그래프로 같은 집합에 있는 모든 사람을

진실을 아는 사람 그룹에 넣어야한다.

 

 

나의 코드

import sys
input = sys.stdin.readline
from collections import deque

n , m = map(int,input().split())
know = set(list(map(int,input().split()))[1:])
party = [list(map(int,input().split()))[1:] for _ in range(m)]

G = [ [] for _ in range(n+1)]
visit = [ False for _ in range(n+1)]

for p in party:
    for pp in p:
        G[pp] += list(set(p)-{pp})

def bfs():
    L = deque(know)
    for i in know:
        visit[i] = True
    while L:
        nn = L.popleft()
        for nnn in G[nn]:
            if not visit[nnn]:
                visit[nnn] = True
                L.append(nnn)

bfs()

count = 0
for p in party:
    check = 0
    for pp in p:
        if  visit[pp]:
            check =1
            break
    if check == 0:
        count+=1
print(count)

 

코드 보완

union-find를 이용해

1. 진실을 아는 사람 그룹을 다 묶는다.

2. 파티에 참여하는 사람 그룹을 다 묶는다. -> 이단계에서 진실을 아는 사람 그룹 , 모르는 그룹이 나눠진다.

3. 파티의 인원이 모두 모르는 그룹일때 count를 센다.

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
n , m = map(int,input().split())
parent = [i for i in range(n+1)]
rank = [1 for _ in range(n+1)]

def fp(x):
    if parent[x] == x:
        return x
    parent[x] = fp(parent[x])
    return parent[x]

def ui(i,j):
    x = fp(i)
    y = fp(j)
    if x != y:
        if rank[x] == rank[y]:
            parent[x] = y
            rank[y] +=1
        elif rank[x] > rank[y]:
            parent[y] = x
        else:
            parent[x] = y

know = list(map(int,input().split()))[1:]
party = [list(map(int,input().split()))[1:] for _ in range(m)]

for i in know[1:]:
    ui(know[0],i)

for p in party:
    for pp in p[1:]:
        ui(p[0],pp)

count = 0
for p in party:
    check = 0
    for pp in p:
        if know:
            if fp(pp) == fp(know[0]):
                check =1
                break
    if check == 0:
        count+=1

print(count)