[Python] 백준1043 거짓말

30 May 2023 in Study on Algorithm

백준1043 거짓말 링크

문제

예제 입력

---

코드

import sys
input = sys.stdin.readline

def find(x):
    if x == parents[x]:
        return x
    return find(parents[x])

def union(x, y):
    x = find(x)
    y = find(y)
    if x < y:
        parents[y] = x
    else:
        parents[x] = y
    
n, m = map(int,input().split())
parents = [i for i in range(n+1)]
_, *tmp = map(int,input().split())

# 진실을 아는 사람의 부모 노드는 0으로 통일
for i in tmp:
    parents[i] = 0

partys = []
for _ in range(m):
    a,*b = map(int,input().split())
    partys.append(b)
    if a == 1:
        continue
    
    # 만난 적 있는 사람들끼리 유니온 파인드
    for i in range(a-1):
        union(b[i], b[i+1])

ans = 0
for party in partys:
    for i in party:
        # 진실을 아는 사람이 있는지 확인
        if find(parents[i]) == 0:
            break
    # break가 안될 시 ans + 1
    else:
        ans+=1
print(ans)

설명

파이썬을 통해서 사용자로부터 입력받아 집합 유니온 파인드 알고리즘으로 파티가 겹치는 사람들을 모두 합쳐 집합을 구성하여 거짓말를 구현했습니다.

---

결과