[백준]1043 거짓말 - C/C++

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

1043번: 거짓말

문제

지민이는 파티에 가서 이야기 하는 것을 좋아한다. 파티에 갈 때마다, 지민이는 지민이가 가장 좋아하는 이야기를 한다. 지민이는 그 이야기를 말할 때, 있는 그대로 진실로 말하거나 엄청나게 과장해서 말한다. 당연히 과장해서 이야기하는 것이 훨씬 더 재미있기 때문에, 되도록이면 과장해서 이야기하려고 한다. 하지만, 지민이는 거짓말쟁이로 알려지기는 싫어한다. 문제는 몇몇 사람들은 그 이야기의 진실을 안다는 것이다. 따라서 이런 사람들이 파티에 왔을 때는, 지민이는 진실을 이야기할 수 밖에 없다. 당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 지민이는 이런 일을 모두 피해야 한다.

사람의 수 N이 주어진다. 그리고 그 이야기의 진실을 아는 사람이 주어진다. 그리고 각 파티에 오는 사람들의 번호가 주어진다. 지민이는 모든 파티에 참가해야 한다. 이때, 지민이가 거짓말쟁이로 알려지지 않으면서, 과장된 이야기를 할 수 있는 파티 개수의 최댓값을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 사람의 수 N과 파티의 수 M이 주어진다.

둘째 줄에는 이야기의 진실을 아는 사람의 수와 번호가 주어진다. 진실을 아는 사람의 수가 먼저 주어지고 그 개수만큼 사람들의 번호가 주어진다. 사람들의 번호는 1부터 N까지의 수로 주어진다.

셋째 줄부터 M개의 줄에는 각 파티마다 오는 사람의 수와 번호가 같은 방식으로 주어진다.

N, M은 50 이하의 자연수이고, 진실을 아는 사람의 수는 0 이상 50 이하의 정수, 각 파티마다 오는 사람의 수는 1 이상 50 이하의 정수이다.

출력

첫째 줄에 문제의 정답을 출력한다.

---

disjoint set을 사용하여 풀 수 있는 문제이다. disjoint set을 생성한 다음에 진실을 알고 있는 사람들은 rank를 1로 초기화 하였다. 그 다음 파티를 순회하며 한 파티에 참석하는 사람들을 모두 Union 해준다. Union 함수는 인자 2개(x,y)를 받아 x, y의 부모를 Find를 통해 찾는다. 여기서 Find 함수는 path compression 기법을 사용하여 이후 Find 함수의 성능을 향상시켰으며, default 값으로는 x의 부모를 y로 설정하지만 만약 x의 rank가 1이라면 y의 부모를 x로 설정한다. 이렇게 같은 집합의 최상위 노드의 rank == 1이라면 진실을 아는 집합일 것이고 rank==0 이라면 진실을 모르는 집합이 될 것이다. 그 후 파티를 다시 순회하며 진실을 아는 사람이 1명이라도 있는지 확인을 한다. 만약 한명이라도 진실을 알고 있는 집합의 사람이라면 그 파티에서 지민이는 거짓말을 하지 못한다. 모든 파티의 사람들이 진실을 모르는 집합의 사람들일 때만 cnt 의 값을 증가시켜준다.

 

#include <iostream>
#include <algorithm>
using namespace std;

int N, M, T,cnt=0;
typedef struct node {
	int parent;
	int rank;
}NODE;
int party[51][51] = { 0 };
NODE ds[51];

int Find(int a) {
	if (a == ds[a].parent)
		return a;
	return ds[a].parent = Find(ds[a].parent);
	
}
void Union(int a, int b) {
	int x = Find(a);
	int y = Find(b);
	if (x == y)
		return;
	if (ds[x].rank == 1) {
		ds[y].parent = x;
	}
	else {
		ds[x].parent = y;
	}
}

void solve() {
	for (int i = 0; i < M; i++) {
		for (int j = 2; j <= party[i][0]; j++) {
			Union(party[i][1], party[i][j]);
		}
	}
	for (int i = 0; i < M; i++) {
		for (int j = 1; j <= party[i][0]; j++) {
			if (ds[ Find(party[i][j]) ].rank)
				break;
			else if (j == party[i][0]) {
				cnt++;
			}
		}
	}
	cout << cnt;
}
int main() {
	cin >> N >> M;
	cin >> T;
	for (int i = 0; i < T; i++) {
		int tmp;
		cin >> tmp;
		ds[tmp].rank = 1;
	}
	for(int i=1;i<=N;i++)
		ds[i].parent = i;
	for (int i = 0; i < M; i++) {
		cin >> party[i][0];
		for (int j = 1; j <= party[i][0]; j++)
			cin >> party[i][j];
	}

	if (T == 0)
		cout << M;
	else 
		solve();
	
	return 0;
}

---

문제를 보자마자 이 문제는 disjoint set을 사용하며 풀면 되겠다는 생각을 하였다. 그래서 학기 중에 배운 Union-Find를 사용하여 구현하였다. 학기 중에는 linked-list를 사용하여 disjoint set을 구현하였지만 백준문제이므로 구현이 쉬운 배열을 사용하였다. Find 함수에서는 수업에서 배운 path compression을 사용하였으며 cnt를 출력하기 전에 각 원소들의 parent를 출력해보았을 때 그 parent는 최상위 노드를 가리키고 있었다.

저번 방학때 union find를 사용하여 푸는 문제를 만났을 때는 굉장히 오래 고민하다가 결국 \구글링 하여 코드를 작성하였다. 그때는 이런 자료구조를 사용하는 문제가 있다는 것에이 놀라웠고 갈 길이 멀다고 생각했다. 하지만 이번에는 문제를 보자마자 disjoint set 을 활용한 union-find 기법을 사용하면 되겠다라는 생각이 바로 든 것으로 보아 학기 중에 알고리즘 수업으로 생각의 폭이 넓어졌다는 것을 느껴 굉장히 뿌듯해졌다! 

 

지금의 블로그 글 구성은 [ 문제 -> 코드의 설명 -> 문제 풀이 과정에서 느낀 생각들]의 순서로  구성이 되어있다. 하지만 누군가 문제를 풀지 못해 내 글을 읽었을때 과연 <코드의 설명> 부분을 읽고 이해를 할 수 있을지 의문이 들었다. 만약 union find 라는 것을 몰라 disjoint set,path compression, rank를 이해하지 못했다면 내 글을 이해하지 못할 것이고 안다 하더라도 저 글을 보고 이해할 수 있을 지는 의문이였다. 그래서 고민을 해보았는데 자료구조를 일일이 설명은 안하더라도 그 자료구조를 알고 있는 사람이 <코드의 설명>부분을 보았을 때 이해가 되는 정도로 글을 작성하도록 노력해봐야겠다!