💻 백준 1043번: 거짓말

문제 소개 🧐

지민이는 파티광이다. 파티마다 가서 자기가 가장 좋아하는 이야기를 하는데, 사실대로 말하거나 과장해서 말한다. 과장이 훨씬 재밌지만, 거짓말쟁이로 몰리기는 싫다. 몇몇 사람들은 이야기의 진실을 알고 있어서, 그들이 파티에 오면 진실만을 말해야 한다. 한 사람이라도 같은 이야기를 다른 파티에서 다르게 들으면 거짓말쟁이가 되므로, 이 상황을 피해야 한다.

결론적으로, 진실을 아는 사람과 한 파티에 같이 있었던 사람은 진실을 알게 되고, 이 사람들이 참석한 다른 파티에서도 진실을 말해야 한다. 이 조건을 모두 만족하면서, 과장된 이야기를 할 수 있는 파티의 최대 개수를 구해야 한다.

입력 📝

  • 첫째 줄: 사람 수 N, 파티 수 M
  • 둘째 줄: 진실을 아는 사람의 수와 그들의 번호
  • 셋째 줄부터 M개 줄: 각 파티에 오는 사람의 수와 그들의 번호

출력 📤

  • 과장된 이야기를 할 수 있는 파티 개수의 최댓값을 출력한다.

첫 번째 시도: Set으로 진실 전파하기 👊

Idea

진실을 아는 사람과 한 번이라도 같은 파티에 있으면, 그 사람도 진실을 알게 된다. 이 관계는 연쇄적으로 이어진다. 이 아이디어를 set을 이용해 구현했다.

  1. 진실을 아는 사람 set 만들기: 처음 주어진 진실을 아는 사람들을 truth_set에 넣었다.
  2. 진실 전파:
    • 모든 파티를 계속 순회했다.
    • 만약 파티에 truth_set에 속한 사람이 한 명이라도 있으면, 그 파티의 모든 참석자를 truth_set에 추가했다.
    • truth_set이 더 이상 변하지 않을 때까지 이 과정을 반복했다.
  3. 결과 계산:
    • 모든 파티를 다시 확인했다.
    • 파티의 참석자 중 단 한 명도 truth_set에 없다면, 그 파티에서는 과장된 이야기를 할 수 있다. 이 파티의 수를 세었다.

Code

import sys

n, m = map(int, sys.stdin.readline().split())
truth_li = list(map(int, sys.stdin.readline().split()))
party_li = [list(map(int, sys.stdin.readline().split()))[1:] for _ in range(m)]

truth_set = set(truth_li[1:])

everyone_in_truth = False

while not everyone_in_truth:  # 진실을 아는, 알게 될 사람을 모두 찾는다
    everyone_in_truth = True
    for i in range(m):
        party_set = set(party_li[i])
        if len(party_set) == len(party_set - truth_set):  # party에 진실을 아는 자가 없는 경우
            continue
        elif len(party_set - truth_set) == 0:  # 파티의 모두가 진실을 아는 경우
            continue
        else: # 파티에 진실을 아는자와 모르는 자가 섞여 있는경우
            truth_set.update(party_set)
            everyone_in_truth = False

answer = 0

for party in party_li:  # 이제 완성된 진실 셋 을 가지고 비교
    party_set = set(party)
    if len(party_set) == len(party_set - truth_set):
        answer += 1

print(answer)

Result

  • 성공! 🎉

개선할 부분 🤔

  • 코드가 좀 길고, while 루프와 for 루프를 여러 번 쓰는 게 비효율적으로 보였다.
  • everyone_in_truth 같은 플래그 대신, truth_set의 크기 변화를 직접 비교하는 게 더 깔끔했을 것 같다.

set 자료구조 덕분에 진실이 퍼져나가는 과정을 쉽게 구현할 수 있었다. 복잡해 보이는 관계도 집합 연산으로 간단히 풀 수 있다는 걸 다시 한번 느꼈다.