[백준] 1043번 거짓말

1. Approach

 

(1) 재귀 + Union Find 알고리즘 으로 접근한다.

 

2. DP[N][M] : n 명의 사람이 m개의 파티를 참가할 때 지민이가 최대한 과장되게 이야기를 할 수 있는 파티 개수의 최댓값. ( 이 문제에서 시간이 충분해서 DP는 큰 의미가 없다 )

 

-> DP[N][4] : N행, 1 - 3 열까지의 정점까지는 오는데에 필요한 최소 비용

 

(3) 풀이 방법

 

해결 방법 : #UnionFind 알고리즘을 사용한다. ( #서로소집합 )

​

(1) 진실을 알고있는 사람들과 같은 파티에 참가한 사람들을 모두 그래프로 잇는다.

(2) 그래프가 이어진 사람들에게는 지민이가 과장된 이야기 ( 거짓말 )를 할 수가 없다.

(3) 그래프가 이어진 사람들을 알고있는 사람들이라고 전부 생각하고 조건을 두면 해결할 수 있다.

​

※ Union Find 알고리즘은 그래프 알고리즘에서 매우 많이 쓰이고 여러 알고리즘의 기반이 되므로 공부하시길 권장합니다.

 

만약 위 알고리즘을 모른 상태로 아래 코드를 본다면 지민이가 과장된 이야기를 할 수 없는 사람들을 전부 연결해놨다고 가정하면 될것입니다.

2. Source Code

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#define MAX 51
using namespace std;
// https://www.acmicpc.net/problem/1043

int n, m;
int nknown;
bool known[MAX];
vector<int> partyinfo[MAX];
int dp[MAX][MAX];

//////////////////////////////////// 아래 함수 3개는 Union Find 알고리즘을 위한 함수
// x의 부모 노드를 찾는 함수			<< 부모 노드를 갱신해주는 함수

// Union Find 알고리즘으로 서로 연결되어있나 확인해본다.
int parent[MAX];
int getParent(int parent[], int x)
{
	// 해당 부모 값과 x값이 같은 경우
	if (parent[x] == x) return x;			// 1로 모두 연결하면 이 부분을 통과하는 것은 1이될 것이다.
	// 최종 부모를 찾는 과정
	return parent[x] = getParent(parent, parent[x]);
}

// 두 부모 노드를 합치는 함수		<< 노드간에 연결해주는 함수
void unionParent(int parent[], int a, int b)
{
	a = getParent(parent, a);
	b = getParent(parent, b);
	if (a < b) parent[b] = a;
	else parent[a] = b;
}

// 같은 부모를 가지는지 확인		<< 노드간에 간선으로 이뤄져있는지 확인하는 함수
int findParent(int parent[], int a, int b)
{
	a = getParent(parent, a);
	b = getParent(parent, b);

	if (a == b) return 1;
	return 0;
}
//////////////////////////////////// 위 3개 함수는 Union Find 알고리즘을 위한 함수


int solution(int peopleidx, int partyidx)
{
	// 파티에서 거짓말할 수 있는 경우
	if (peopleidx == 0) return 1;

	int& result = dp[peopleidx][partyidx];
	if (result != -1)
		return result;

	result = 0;
	// 현재 peopleidx인 사람이 거짓말을 알고 있고
	if (known[peopleidx])
	{
		// 이 파티에 참가해있는 인원들을 확인해본다
		for (int i = 0; i < partyinfo[partyidx].size(); i++)
		{
			if (peopleidx == partyinfo[partyidx][i])
			{
				// 이 경우 거짓말을 할 수 없는 파티가 된다.
				return 0;
			}
		}
		// 파티에 참가해있는 인원중 없는 인원이라면 가능

		result = solution(peopleidx - 1, partyidx);
	}
	else {
		// 모르는 사람이라면 가능
		result = solution(peopleidx - 1, partyidx);
	}

	return result;
}

int main()
{
	cin >> n >> m;
	cin >> nknown;
	vector<int> knownclub;
	for (int i = 1; i <= n; i++)
	{
		parent[i] = i;
	}
	for (int i = 1; i <= nknown; i++)
	{
		int people; cin >> people;
		knownclub.push_back(people);
		known[people] = true;
	}
	for (int i = 1; i <= m; i++)
	{
		int many, who; cin >> many;
		for (int j = 0; j < many; j++)
		{
			cin >> who;
			partyinfo[i].push_back(who);
			// 같은 파티에 참가하는 인원끼리 전부 그래프로 엮어준다.
			unionParent(parent, partyinfo[i][0], partyinfo[i][j]);
		}
	}
	// 사실을 알고있는 사람과 엮인 사람들의 known 배열을 전부 true로 바꿔준다.
	for (int j = 0; j < knownclub.size(); j++)
	{
		for (int i = 1; i <= n; i++)
		{
			// 엮인 경우
			if (findParent(parent, knownclub[j], i) == 1)
			{
				known[i] = true;
			}
		}
	}

	int ans = 0;
	for (int i = 1; i <= m; i++)
	{
		memset(dp, -1, sizeof(dp));
		ans += solution(n, i);
	}
	cout << ans << endl;
	return 0;
}

3. 비슷한 문제

1. DFS 관련 문제

4. 참조

---

www.acmicpc.net/problem/1043