[백준] 1043 - 거짓말

1. 문제

1043번: 거짓말

2. 개요

파티에 가서 한 이야기를 하려고 한다. 이 이야기를 되도록이면 과장해서 말하려고 한다.

하지만 진실을 알고 있는 사람이 있어서, 진실을 알고 있는 사람이 속한 그룹에서는 진실된 이야기를 할 수 밖에 없다. 또한 어떤 사람이 진실된 이야기를 듣고, 과장된 이야기를 듣는 것도 피하려고 한다.

이 때, 과장된 이야기를 할 수 있는 최대 횟수를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

먼저 진실된 이야기를 알고 있는 사람들을 집합으로 만든다.

이후 주어진 그룹들을 충분히 탐색하며, 진실된 이야기를 아는 그룹과 교집합이 존재한다면 해당 그룹의 모든 원소를 진실된 이야기를 아는 그룹과 합친다.

다시 한번 모든 그룹들을 탐색하며 진실된 이야기를 아는 그룹과 교집합이 존재하지 않는 경우에만 답을 1늘려준다.

탐색이 끝났다면 답을 출력한다.

3-2. Python

import sys

answer = 0

N, M = map(int, sys.stdin.readline().split())

knowtruth = set(list(map(int, sys.stdin.readline().split()))[1:])
party = []

for i in range(M):
    people = list(map(int, sys.stdin.readline().split()))[1:]
    party.append(people)

for i in range(M):
    for j in range(len(party)):
        chk = knowtruth.intersection(set(party[j]))

        if len(chk) > 0:
            knowtruth = knowtruth.union(set(party[j]))

for p in party:
    if len(knowtruth.intersection(p)) > 0:
        continue

    answer += 1

print(answer)

3-3. C#

namespace boj_1043
{
    internal class Program
    {
        static void Main(string[] args)
        {
            StreamReader sr = new StreamReader(Console.OpenStandardInput());
            StreamWriter sw = new StreamWriter(Console.OpenStandardOutput());

            int answer = 0;

            string[] input = sr.ReadLine().Split();
            int N = int.Parse(input[0]);
            int M = int.Parse(input[1]);

            HashSet<int> knowtruth = new HashSet<int>(Array.ConvertAll(sr.ReadLine().Split()[1..], int.Parse));
            List<List<int>> party = new List<List<int>>();

            for (int i = 0; i < M; i++)
            {
                List<int> people = new List<int>(Array.ConvertAll(sr.ReadLine().Split()[1..], int.Parse));
                party.Add(people);
            }

            for (int i = 0; i < M; i++)
            {
                for (int j = 0; j < party.Count; j++)
                {
                    HashSet<int> chk = new HashSet<int>(knowtruth.Intersect(party[j]));

                    if (chk.Count > 0)
                        knowtruth.UnionWith(party[j]);
                }
            }

            foreach (List<int> p in party)
            {
                if (knowtruth.Intersect(p).ToList().Count > 0)
                    continue;

                answer++;
            }

            sw.WriteLine(answer);
            sw.Close();
        }
    }
}