[백준] 1043번 거짓말 - python 파이썬

문제

 

 

 

이 문제는 문제를 이해하는데 오래걸렸던 문제이다....

처음에는 단순하게 진실을 아는 사람이 속해있는 파티라면 참여를 못한다 생각했는데 당연히 오답이였다..

 

 

문제를 읽으면 알 수 있듯이 진실을 아는 사람이 파티에 속해있으면 진실을 몰랐던 사람도 이 파티에서 지민이가 진실을 말하기때문에 진실을 아는 사람이 된다.

 

 

즉, 진실을 아는 사람과 같은 집합이라면 진실을 아는 집합이 되는거다.

 

 

이런 패턴 어디서 많이 본 패턴이다. 바로 분리 집합

 

물론 이 문제는 집합 연산자로도 풀어줄 수 있는 문제이긴하나 Union-Find를 활용해서도 풀어주었다.

 

기존의 Union-Find는 대소비교로 작은값 또는 큰 값을 기준으로 union을 해줬다면 이 문제에서는 값의 크기를 기준으로 어떤 부모에 합쳐줄지 정하기 이전에

 

진실을 아는 집합에 속한 사람을 부모로 가진다면 이 부모로 union을 해주어야한다. (이 부분이 가장 어려운 것 같다 응용하는게 중요!)

 

그렇게 해주면 아래와 같이 나오게 된다

 

 

예시

8 5
3 1 2 7
2 3 4
1 5
2 5 6
2 6 8
1 8
>>[0, 1, 2, 3, 3, 5, 5, 7, 5] #Parent

 

 

 

4 5
1 1
1 1
1 2
1 3
1 4
2 4 1
>>[0, 1, 2, 3, 1]#Parent

 

정답 코드(Union-Find버전)

def union(a,b):
    a = find(a)
    b = find(b)
    #둘다 진실을 아는 경우에는 union종료
    if a in truep and b in truep:
        return
    if a in truep:
        parent[b] = a
    elif b in truep:
        parent[a] = b
    else:
        if a < b:
            parent[b] = a
        else:
            parent[a] = b

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

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

parties = []
for _ in range(m):
    party = list(map(int,input().split()[1:]))
    parties.append(party)
    for i in range(len(party)-1):
        union(party[i],party[i+1])


ans = 0
for party in parties:
    for p in party:
        #parent[p]가 최종 부모가 아닐 수 있으므로 find를 통해 확인
        if find(p) in truep:
            break
    else:
        ans += 1
print(ans)

 

 

 

이때 처음에 마지막에 find(p)가 아닌 parent[p]를 통해 현재의 사람이 진실을 아는 집합에 속하는 지 확인하려 해서 계속 오답이 발생했다....

 

parent[p] 가 최종 부모가 아닌 중간단계의 부모일 수도 있기 때문에 find를 통해 최종 부모를 찾아주는게 필요하다.

 

만약 parent[p]로 확인하고 싶다면 아래처럼 확인하기 이전에 경로압축을 해주어야 한다.

 

# 경로 압축을 적용하여 parent 배열을 최적화
for i in range(1, n+1):
    find(i)  # 모든 노드에 대해 `find`를 호출하여 경로 압축 적용

 

 

 

정답코드(집합 연산자 활용)

n, m = map(int,input().split())
truep = 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 & truep:
            truep = truep.union(party)
ans = 0
for party in parties:
    if party & truep:
        continue
    ans += 1
print(ans)

 

 

집합연산자를 통해서 더욱 간단하게 해결해줄 수도 있다.