C++ 백준 1043 거짓말

백준 1043

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

1043번: 거짓말

풀이 전 나의 생각

이야기의 진실을 알고 있는 사람과 각 파티의 사람 정보가 주어질 때

지민이가 과장되게 말할 수 있는 파티의 수를 구해야 한다.

 

조건

- N, M은 50 이하의 자연수

- 진실을 아는 사람의 수는 0 이상 50 이하의 정수

- 파티마다 오는 사람의 수는 1 이상 50 이하의 정수

 

과정

진실을 알고 있는 사람이 3이고 파티에 같이있는 사람이 4라면

4는 이야기가 진실이라는 것을 알 수 있다. 그럼 4도 다른 파티장에

갔을 때, 4와 같이 있는 파티 사람에게 이야기의 진실을 알려줄 수 있다.

 

이러한 형태를 보면 그래프의 형태가 나오게 되는데 이야기의 진실을

알고 있는 사람으로부터 연결 되어있는 모든 사람이 저장된 그래프를 탐색하며

진실을 알게된 사람을 모두 체크해주면된다.

 

사실 이 문제는 그래프보다 유니온 파인드를 이용하여 부모를 기준으로

그룹을 합병하는 것이 훨씬 간단하고 풀기쉽다.

 

하지만 그래프로 푸는 방법을 알고있다면 유니온 파인드의 내용이 갑자기

기억이 안날 때 유용할 것 같아서 DFS와 그래프를 이용하여 풀이를 진행했다.

 

과정은 다음과 같다.

1. 각 파티에 있는 사람, 진실을 알고 있는 사람, 각 파티에 있는 모든 사람을 연결한 그래프 저장

2. 진실을 알고있는 사람들의 DFS 탐색을 진행하며 연결된 모든 사람을 따로 체크

3. 각 파티에 있는 사람을 체크하면서 진실을 알고 있는지, 아닌지 체크

풀이

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
#include <string>
#include <queue>
#include <string.h>
#include <limits.h>
#include <cstdio>
#include <map>

using namespace std;

vector<vector<int>>link(51);
vector<vector<int>>input(51);

bool visited[51];
bool true_v[51];

void dfs(int st)
{
	visited[st] = true;
	true_v[st] = true;
	for (int next : link[st])
	{
		if (!visited[next])
		{
			dfs(next);
		}
	}
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	vector<int>true_p;
	int N, M, T;

	cin >> N >> M >> T;

	int ans = M;

	if (T != 0)
	{
		for (int i = 0; i < T; i++)
		{
			int u;
			cin >> u;

			//진실을 알고 있는 사람 저장
			true_p.push_back(u); 
		}
	}

	for (int i = 0; i < M; i++)
	{
		int n = 0, prev = 0;
		cin >> n;

		for (int j = 0; j < n; j++)
		{
			int h;
			cin >> h;

			//각 파티에 있는 사람 저장
			input[i].push_back(h);

			if (j == 0)
			{
				prev = h;
			}
			else
			{
				//모든 파티에 있는 사람의 관계 저장
				link[prev].push_back(h);
				link[h].push_back(prev);
				prev = h;
			}
		}
	}

	if (T != 0)
	{
		for (int val : true_p)
		{
			//진실을 알고 있는 사람과 관련된 사람을 체크하기 위해 DFS 탐색 진행
			fill(visited, visited + 51, false);
			dfs(val);
		}

		//각 파티의 사람들이 진실을 알고 있는지, 아닌지 체크
		for (int i = 0; i < M; i++)
		{
			for (int val : input[i])
			{
				if (true_v[val])
				{
					ans--;
					break;
				}
			}
		}

		cout << ans;
	}
	else
	{
		cout << ans;
	}
}