[백준 1043번] 파이썬 - 거짓말

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

1043번: 거짓말

 

 

# 조건

• 지민이는 썰을 풀 때, 있는 그대로 또는 엄청나게 과장해서 말한다.
• 되도록이면 과장해서 이야기하려고 하는데 거짓말쟁이는 싫다.
• 몇몇 사람들은 그 이야기의 진실을 알기 때문에 이 사람들이 파티에 온다면 진실만을 이야기 해야 한다.
• 당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 다른 파티에서는 과장된 이야기를 들었을 때도, 지민이는 거짓말쟁이가 된다.
• 사람의 수 N이 주어지고 그 이야기의 진실을 아는 사람이 주어진다.
• 각 파티에 노느 사람들의 번호가 주어지며, 지민이는 모든 파티에 참가
• 이 때, 지민이가 거짓말쟁이로 알려지지 않으면서, 과장된 이야기를 할 수 있는 파티 개수의 최댓값을 구하라.

 

# 입력

• 첫째 줄에 사람의 수 N과 파티의 수 M이 주어진다.
• 둘째 줄에는 이야기의 진실을 아는 사람의 수와 번호가 주어진다. 진실을 아는 사람의 수가 먼저 주어지고 그 개수만큼 사람들의 번호가 주어진다. 사람들의 번호는 1부터 N까지의 수로 주어진다.
• 셋째 줄부터 M개의 줄에는 각 파티마다 오는 사람의 수와 번호가 같은 방식으로 주어진다.
• N, M은 50 이하의 자연수이고, 진실을 아는 사람의 수는 0 이상 50 이하의 정수, 각 파티마다 오는 사람의 수는 1 이상 50 이하의 정수이다.

 

# 접근 방법

• 단순히 진실을 아는 사람의 번호가 들어있는 파티만 제외해주면 될 것 같지만,
• 진실을 아는 사람과 같이 파티를 갔던 사람들도 제외해주어야 한다.
• 그래프를 이용하여 서로의 상관 관계를 기록해준 후 표를 이용하여 파티의 수를 구해주면 될 것 같다.
• 부모 노드를 찾아주어야 하므로 집합을 찾고 합하는 UNION, FIND를 통해 체크를 해준다.

 

틀린 코드

- 만난 사람이 만난 사람을 체크해주지 않았다.

import sys  
sys.stdin = open('input.txt')  
  
  
  
N, M = map(int, input().split())  
true = [*map(int, input().split())]  
del true[0]  
  
person = [0] * (N+1)  
  
  
result = 0  
  
# 진실 아는 사람이 0이라면 바로 출력  
if not true:  
    print(M)  
# 아니라면 진실 아는지 여부 체크  
else:  
    party = []  
    for _ in range(M):  
        # 각 파티마다 참가 번호 기록 및 전체 party에 추가  
        number = [*map(int, input().split())]  
        party.append(number)  
        # 전체 인원 중 진실을 아는 번호가 있다면  
        for i in range(1, number[0]+1):  
            if number[i] in true:  
                # 해당 파티의 인원은 모두 1로 변경 후 반복문 종료  
                for j in range(1, number[0]+1):  
                    person[number[j]] = 1  
                break  
  
  
    for k in party:  
        # 해당 파티의 인원  
        num = k[0]  
        for l in range(1, num + 1):  
            if person[k[l]] == 1:  
                break  
        else:  
            result += 1  
  
    print(person)  
    print(result)

 

정답 코드

• 따라서 그래프 탐색을 원소가 속한 집합을 찾아주어 체크 해주었다.
  • 진실을 아는 사람의 부모 노드는 0으로 통일
  • 부모 노드가 작은 쪽으로 통합하기 때문에 진실을 아는 사람의 뿌리 노드는 모두 0

import sys  
sys.stdin = open('input.txt')  
  
  
def union(x,y):  
    x = find(x)  
    y = find(y)  
    if x < y:  
        parents[y] = x  
    else:  
        parents[x] = y  
  
# 특정 원소가 속한 집합 찾기  
def find(z):  
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀 호출  
    if z == parents[z]:  
        return z  
    return find(parents[z])  
  
N, M = map(int, input().split())  
  
# 집합 기록할 리스트  
parents = [i for i in range(N+1)]  
  
a, *true = map(int, input().split())  
if a == 0:  
    print(M)  
else:  
    for i in true:  
        # 1차 진실을 아는 사람 0으로 만들어주기  
        parents[i] = 0  
  
    party = []  
    for j in range(M):  
        num, *number = map(int, input().split())  
        party.append(number)  
        # 참가 인원 혼자라면 집합 찾아줄 필요 x  
        if num == 1:  
            continue  
  
        # 아니라면 연관된 집합 기록해준다.  
        for k in range(num-1):  
            union(number[k], number[k+1])  
  
    result = 0  
  
    for l in party:  
        for u in l:  
            if find(parents[u]) == 0:  
                break  
  
        else:  
            result += 1  
  
    print(result)