백준 1043 - UNION FIND

1043 파이썬으로 union - find 를 통해 해결

거짓말을 할수 있는 사람과 아닌 사람으로 그룹을 2분화 할 수 있다. 2개의 집합은 서로소의 관계이다.

따라서 union - find 알고리즘을 통해 문제를 해결한다.

Union & Find?

node 에 대해 배열을 선언한 후에 (굳이 트리로 구현을 할 필요는 없다)

parent ( 자기 위의 조상을 만들 리스트 ) 를 생성 후에 자신의 parent 노드를 담는다

초기 값으로는 자기 자신이다.

Find 함수를 통해 자신의 최고 root를 찾고 같은 집합으로 만들 다른 노드를 union한다.

코드로 살펴보자

# Find
def find(a):
	global parent
    if(parent[a] == a):
    	return a
    else:
    	find(parent[a])
        
# Union
def Union(a, b):
	global parent
    pa = find(a)
    pb = find(b)
    # 조상이 같지 않다면 현재 다른 집합으로 간주 되므로 합쳐서 같은 조상이 되도록 만든다
    if(pa != pb):
    	# 노드 번호가 작은 쪽으로 조상을 만든다 큰쪽으로 만들어도 상관이 없다.
    	if(pa < pb):
        	parent[pb] = pa
        eles:
        	parent[pa] = pb

 

그에 따른 나의 1043 구현은 다음과 같다.

# 진실 듣고 과장된 이야기 들으면 거짓말쟁이
# 과장된 이야기 듣고 진실 들어도 거짓말쟁이
# 과장된 이야기 들은 사람은 과장된 이야기만, 진실 들은 사람은 진실 이야기만
# 파이썬에서의 set은 변경 불가능한 값 또는 객체의 모음 => 튜플 + 상수만 된다고 생각
# 따라서 추가할 때는 add, 만약 튜플에있는 요소에대해 추가 update 사용
# 이분법 사고 인데, 트리 구현을 어떻게 사용하는 것이 편안한가?

import sys

def find(x):
    global tree
    if(tree[x] == x):
        return x
    else:
        return find(tree[x])

def union(x, y):
    global tree
    px = find(x)
    py = find(y)
    if(px != py):
        tree[px] = py


N, M = map(int, input().split())
tree = list(i for i in range(N + 1))
truth = list(map(int, sys.stdin.readline().rstrip().split()))
if(truth[0] == 0):
    for i in range(M):
        sys.stdin.readline().rstrip().split()
    print(M)
else:
    root = truth[1]
    cmp = []
    cnt = 0
    P = set()
    for i in truth[2:]:
        tree[i] = root
    for i in range(M):
        val = list(map(int, sys.stdin.readline().rstrip().split()))
        if(val[0] == 0):
            continue
        elif(val[0] == 1):
            cmp.append(set([val[1]]))
        else:
            temp = set(map(int, val[1:]))
            cmp.append(temp)
            for j in range(1, val[0]):
                union(val[j], val[j + 1])

    root = find(root)
    P.add(root)
    for i in range(N + 1):
        if(find(i) == root):
            P.add(i)

    for i in range(M):
        if(P & cmp[i] == set()):
            cnt += 1
    print(cnt)

물론 union - find 안쓰고 계속 순회하면서 P(거짓말을 못하는 대상) 을 최신화 시켜도 된다. set.update 를 이용