[BOJ/백준] 1043 거짓말 - 파이썬

문제

진실을 알고 있는 사람이 파티에 오는 경우, 진실을 알고 있는 사람과 같은 파티에 왔던 사람이 다른 파티에 오는 경우, 거기에 있는 다른 사람이 참석하는 또 다른 파티의 경우 등이 존재하는 상황에서 지민이가 과장된 이야기를 할 수 있는 파티 수의 최댓값을 구하는 문제.

 

 

문제풀이

Union-Find 알고리즘으로 풀이

지민이가 과장된 이야기를 할 수 없는 사람들을 하나의 집합으로 구성

 

ffind 함수로 해당 원소의 parent 원소를 찾는다.

union 함수로 진실을 아는 사람들과 그와 같이 파티에 오는 사람들(연쇄적)을 하나로 묶는다.

- 입력받은 두 원소가 모두 진실을 아는 사람 -> 변화 X

- 둘 중 한 원소가 진실을 아는 사람 -> 진실을 아는 사람을 부모로 갱신

- 둘 다 진실을 아는 사람이 아님 -> 대소 관계에 따라 부모 관계 부여 (후에 갱신될 수 있으므로)

 

 

코드

import sys
input=sys.stdin.readline


def find(parent,x):
    if x!=parent[x]:
        parent[x]=find(parent,parent[x])
    return parent[x]

def union(parent,a,b,mem):
    a=find(parent,a)
    b=find(parent,b)

    if a in mem and b in mem:
        return

    if a in mem:
        parent[b]=a
    elif b in mem:
        parent[a]=b

    else:
        if a<b:
            parent[b]=a
        else:
            parent[a]=b

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

b=list(map(int,input().split()))[1:]
##아는 사람 

g=[]
parent=list(range(n+1))

for i in range(m):
    temp=list(map(int,input().split()))
    people=temp[1:]
    
    for j in range(temp[0]-1):
        union(parent,people[j],people[j+1],b)
    g.append(temp[1:])
    
    
result=0

for i in g:
    for j in range(len(i)):
        if find(parent,i[j]) in b:
            break
    else:
        result+=1

print(result)

 

 

기타

만약 집합을 이용하여 푼다면 순차적으로 탐색하는 경우, 후에 새롭게 하나로 묶이게 되는 경우가 발생할 수 있어서 다시 모든 파티를 재탐색해야하므로 모든 경우를 탐색할 수 있어야한다. (그에 따른 새로운 경우가 발생 시 또 다시 탐색)

  ->시간 초과에 걸리지 않도록 주의