[백준 파이썬 소로소 집합]1043 거짓말

[백준 파이썬 소로소 집합]1043 거짓말

 

문제

주인공은 파티 가서 이야기하는 것을 좋아한다. 파티에 갈 때마다 자신의 이야기를 과장해서 말한다. 하지만 거짓말쟁이로 알려지기 싫어한다. 문제는 몇몇 사람들이 이야기의 진실을 알고 있다 그렇기에 진실을 알고 있는 사람들이 있을 때에는 진실을 이야기할 수밖에 없다. 당연히 어떤 사람이 어떤 파이테서는 진실을 듣고 또 다른 파티에서는 과장된 이야기들을 들었을 때도 주인공은 거짓말쟁이로 알려지게 된다. 주인공은 이런 일을 모두 피해야 한다.

사람수 n이 주어지고 진실을 아는 사람과 각 파티에 오는 사람들의 번호가 주어진다. 주인공은 모든 파티에 참가해야 한다. 과장된 이야기를 할 수 있는 파티 개수의 최댓값을 구하여라.

입력, 출력

풀이

나는 union find 알고리즘을 이용해서 풀었다.

find라는 함수와  union이라는 함수를 만든다.

find 함수는 현재 내가 속해 있는 그룹을 대표하는 원소를 반환한다.

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

union함수는 두 개의 그룹을 하나의 그룹으로 합치는 작업을 한다.

def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)




    if a < b:
        parent[b] = a

    else:
        parent[a] = b

 

union함수를 이용하여 현재 파티에 참석하는 사람들을 하나의 그룹으로 묶을 수 있다 이때 진실을 아는 사람이 있다면 

진실을 아는 사람을 대표로 하는 그룹으로 만들어야 한다.

 

나는 여기까지 생각했는데 union함수를 수정하지 않고 union함수를 실행하기 전에 여러 조건을 추가해서 해보려 했지만 실패하고 어쩔 수 없이 다른 사람의 풀이를 봐야 했다.

다른 사람들 풀이를 보니까 union 함수 내부에서 내가 하려던 걸 매우 간편하게 처리하는 것을 보고 허탈하긴 했다

 

간단히 말하면 위 union함수에서는 진실을 아는 사람이 a, b두 원소중 하나라도 있다면 무조건 진실을 아는 사람을 대표로 만들면 된다. 만약 진실을 아는 사람이 없는 경우에는 원래 union함수처럼 실행하면 된다.

 

def union_parent(parent, a, b, know_truth):
    a = find_parent(parent, a)
    b = find_parent(parent, b)

    if a in know_truth and b in know_truth:
        return

    if a in know_truth:
        parent[b] = a

    elif b in know_truth:
        parent[a] = b

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

        else:
            parent[a] = b

이렇게 하면 진실을 아는 사람을 무조건 대표로 만들 수 있다.

 

그 후 정답을 출력하기 위해서 각 파티에 참석한 사람들 번호를 가지고 find함수를 이용하여 대표자를 찾아

그 대표자가 진실을 아는 사람들이 나면 다음 파티를 탐색한다. 만약 나오지 않았다면 과장된 이야기를 할 수 있는 파티이기에 +1 해준다.

코드

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


def union_parent(parent, a, b, know_truth):
    a = find_parent(parent, a)
    b = find_parent(parent, b)

    if a in know_truth and b in know_truth:
        return

    if a in know_truth:
        parent[b] = a

    elif b in know_truth:
        parent[a] = b

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

        else:
            parent[a] = b

n,m=map(int,input().split())
know=list(map(int,input().split()))
array=[]
know_s=know[1:]
ans=0
parent=[0]*(n+1)
for i in range(1,n+1):
    parent[i]=i

for i in range(m):
    check=True
    prty=list(map(int,input().split()))
    array.append(prty[1:])

    for j in range(1,prty[0]):
        union_parent(parent,prty[j],prty[j+1],know_s)


for i in range(m):
    check=True
    for j in array[i]:
        a=find_parent(parent,j)
        if a in know_s:
            check = False
            break
    if check:
        ans+=1


print(ans)