백준 1043번(거짓말)

📒 알고 가야 하는 것

- 분리 집합(Union-find): 서로소 집합이라고 하며 공통 원소를 가지지 않는 두 개의 집합을 만들어낸다.
- root 노드를 찾는 작업(Find)
- 두 트리를 병합하는 작업(Union)

📌 DFS

def find(parent, x) :
	if parent[x] != x :
    	x = find(parent, parent[x])
	return parent[x]
    
def union(parent, a, b, know_truth) :
	a = find(parent, a)
    b = find(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
            

📌 코드

import sys
input = sys.stdin.readline


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


def union(parent, a, b, know_truth) :
    a = find(parent, a)
    b = find(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[a] = b
        else :
            parent[b] = a 


n, m = map(int, input().split())

know_truth = list(map(int, input().split()))[1:]
parent = list(range(n+1))

for _ in range(n) :
    party_info = list(map(int, input().split()))
    party_len = party_info[0]
    party = party_info[1:]

    for i in range(party_len - 1) :
        union(parent, party[i], party[i+1], know_truth)

📌 피드백

- dfs에 대해서 그동안 문제를 푼 적이 없었는데 이번 기회에 잘 숙지해야겠다.
- 풀이에 대한 접근은 맞은듯!!