백준 1043

<거짓말>

난이도 : 골드 4

1. 백준 문제

1043

2. 코드 알고리즘

3. 코드

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

import sys
input = sys.stdin.readline

n,m= map(int, input().split())
truth = list(map(int, input().split()))
#truth[0]= 진실을 아는 사람 수
result = 0

def find(a):
    if parent[a] == a:
        return a
    else:
        parent[a] = find(parent[a])
        return parent[a]

def union(a,b):
    parent_a = find(a)
    parent_b = find(b)
    parent[parent_b] = parent_a

# 입력
#party 행렬 형성하기
party = [[0] for i in range(m+1)]
#party = [[0], [0], [0], [0]]
for i in range(1, m+1):
    #각 해당 index에 작성하기
    num = list(map(int, input().split())) #[2, 1, 2]
    for j in range(1, num[0]+1):
        party[i].append(num[j])
        #party = [[0], [0, 1, 2], [0, 3], [0, 2, 3, 4]]
#parent 행렬 초기화하기
parent = [0]
for i in range(1, n+1):
    parent.append(i)

#각 부모노드 파티 대표노드로 설정하기
for i in range(1, m+1):
    for j in range(2, len(party[i])):
        #party[i][0] = 0, party[i][1] = 대표노드
        #이외의 모든노드 대표노드로 맞추기
        union(party[i][1], party[i][j])

#다시 파티행렬을 돌면서 진실 아는 사람의 대표노드와 일치하는지 비교
for i in range(1, m+1):
    check=1
    #각 파티의 대표노드는 항상 party[i][1]
    pivot = find(party[i][1])
    for j in range(1, truth[0]+1):
        #진실 후보들과 비교
        if pivot == find(truth[j]):
            check = 0
            break
    if check == 1:
        result+=1 #각 파티 분기 끝날때마다 result+=1 하기


print(result)#1043
#https://www.acmicpc.net/problem/1043

import sys
input = sys.stdin.readline

n,m= map(int, input().split())
truth = list(map(int, input().split()))
#truth[0]= 진실을 아는 사람 수
result = 0

def find(a):
    if parent[a] == a:
        return a
    else:
        parent[a] = find(parent[a])
        return parent[a]

def union(a,b):
    parent_a = find(a)
    parent_b = find(b)
    parent[parent_b] = parent_a

# 입력
#party 행렬 형성하기
party = [[0] for i in range(m+1)]
#party = [[0], [0], [0], [0]]
for i in range(1, m+1):
    #각 해당 index에 작성하기
    num = list(map(int, input().split())) #[2, 1, 2]
    for j in range(1, num[0]+1):
        party[i].append(num[j])
        #party = [[0], [0, 1, 2], [0, 3], [0, 2, 3, 4]]
#parent 행렬 초기화하기
parent = [0]
for i in range(1, n+1):
    parent.append(i)

#각 부모노드 파티 대표노드로 설정하기
for i in range(1, m+1):
    for j in range(2, len(party[i])):
        #party[i][0] = 0, party[i][1] = 대표노드
        #이외의 모든노드 대표노드로 맞추기
        union(party[i][1], party[i][j])

#다시 파티행렬을 돌면서 진실 아는 사람의 대표노드와 일치하는지 비교
for i in range(1, m+1):
    check=1
    #각 파티의 대표노드는 항상 party[i][1]
    pivot = find(party[i][1])
    for j in range(1, truth[0]+1):
        #진실 후보들과 비교
        if pivot == find(truth[j]):
            check = 0
            break
    if check == 1:
        result+=1 #각 파티 분기 끝날때마다 result+=1 하기


print(result)

4. 코드 후기

유니온파인드 문제들중에 상대적으로 괜찮았던 문제!
앞에 유니온파인드 문제 2개를 푸니 어떻게 적용해야될지 감을 잡은 느낌?
마지막 for문에 check를 초기화하는 것을 깜박해 에러를 잡는데 살짝 시간이 소요됐지만...
해결하고나니 가장 뿌듯한 문제!
슈도코드를 참고 안하고 혼자서 풀어낸 문제기 때문!