[Python] BOJ 1043 - 거짓말

https://www.acmicpc.net/problem/1043

1043번: 거짓말

# Union-Find와 BFS 등 여러 풀이가 있는 문제이다.

 

I. Union-Find

   union, find, check함수는 well-known이니 따로 설명하지 않겠다.

 

   1. 우선 처음에 N, M을 입력받고 진실을 아는 사람수 t와 그 사람들 리스트 tp를 입력받는다.

       tp에 있는 사람들 번호에 해당하는 know_truth[i]를 True로 바꿔준다.

       그리고 M줄에 걸쳐 각 파티마다 오는 사람의 수 p와 명단 pp를 입력받고

       party에 차례대로 append해준다. p가 2이상일 때, 그 파티의 사람들끼리 union해준다.

 

   2. know_truth배열을 돌면서 진실을 아는 사람들끼리 또 묶어준다.

       (know_truth[i]가 참이면 i의 부모를 찾아 know_truth[find(i)]도 True로 바꿔준다.)

       know_truth가 True인 인덱스가 진실을 아는 사람들이다.

 

   3. t가 0이면 모든 파티에서 거짓말을 할 수 있으므로 M을 출력하고

       0이 아니라면, 모든 파티를 반복문을 돌며 파티에 속한 사람들 중 know_truth가 False인 사람이

       1명이라도 존재한다면 continue하고, 모든 사람들이 True라면 answer 1증가시킨다.

 

import sys
input = sys.stdin.readline
def find(c):
	if par[c] == c:
		return c
	else:
		par[c] = find(par[c])
	return par[c]

def union(a, b):
	a, b = find(a), find(b)
	par[max(a, b)] = min(a, b)

def check(a, b):
	return find(a) == find(b)


party = []
N, M = map(int,input().split())
know_truth = [False] * (N+1)
par = [i for i in range(N+1)]
t, *tp = map(int,input().split())
for i in range(t):
    know_truth[tp[i]] = True

for _ in range(M):
    p, *pp = map(int,input().split())
    party.append(pp)
    if p > 1:
        for i in range(p-1):       
            union(pp[i], pp[i+1])

for i in range(1, N+1):
    if know_truth[i]:
        know_truth[find(i)] = True

if t == 0:
    print(M)
    sys.exit(0)
else:
    answer = 0
    for i in party:
        tf = True
        for j in i:
            if know_truth[find(j)]:
                tf = False
        if tf:
            answer += 1
    print(answer)

(solved.ac 티어: 골드 4)