[백준 1043] 거짓말 (C++)

1. 문제

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

1043번: 거짓말

2. 풀이

접근 방법

문제의 조건 중

"어떤 파티에서는 진실을 듣고 또다른 파티에서는 과장된 이야기를 들었을 때에도 거짓말 쟁이로 간주된다"

라는 표현이 핵심 포인트입니다. 저는 이 문제를 해결하는 과정에서 유니온 파인드를 떠올렸습니다.

처음에는 단순히 모든 파티들을 탐색하며 진실/거짓 여부를 확인하고 개수를 세어 주려고 했습니다. 하지만 테스트 케이스를 검증하다가 보니 예외가 존재합니다. 현재 사실을 아는 사람이 없어서 거짓을 말하더라도 이후에 문제가 발생합니다. 다음의 테스트 케이스를 가정해 보겠습니다.

6 4
3 1 2 3
2 1 3
1 4 6
1 5
2 4 1

위의 상황에서 진실을 아는 사람은 {1, 2, 3}이고 총 4번의 파티를 진행합니다.

1. 첫 번째 파티에서는 1, 3모두 진실을 알고 있으므로 진실을 말합니다.
2. 두 번째 파티에서는 거짓, 세 번째 파티에서도 거짓을 말합니다.
3. 네 번째 파티에서는 진실을 아는 1이 있으므로 진실을 말해야 합니다. 여기서 문제가 생깁니다.

이미 두 번째 파티에서 4번에게 거짓을 말했는데 네 번째 파티에서 1때문에 진실을 말하면 4에 의해 거짓말쟁이가 됩니다!

이런 경우 두 번째 파티에 참여했던 4와 6모두 진실로 업데이트해야 합니다.

풀이

여기서 4와 연결되어 있는 사람들을 모두 탐색하며 업데이트시킬 수 있지만 유니온 파인드를 사용하면 O(1)로 업데이트할 수 있습니다. 따라서 집합의 개념을 이용하여 진실을 아는 집합/그 외의 집합으로 분리하고 이후에 수정이 필요한 경우 루트 노드만 업데이트하면 됩니다.

 

3. 구현

유니온 파인드를 이용하여 구현한 알고리즘 순서입니다.

1. 진실을 아는 사람들의 집합의 루트 노드를 0, 거짓인 경우 루트노드를 자기 자신으로 정합니다.
2. 각파티를 입력받으면서 파티에 참여한 사람들끼리 집합을 생성합니다.
3. 이후 각 파티들을 탐색하며 한명이라도 진실을 아는 사람이 있으면 그 집합의 루트 노드를 0(진실)로 업데이트합니다.
4. 마지막으로 각 파티를 탐색하며 그 파티의 집합이 거짓을 나타내는 경우를 세어 답을 출력합니다.

 

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

int N, M, T, ans;
//루트 노드가 0이라면 진실, 아니라면 거짓
int par[51];
vector<vector<int>> party(51);

int Find(int x) {
	return x == par[x] ? x : par[x] = Find(par[x]);
}

void Union(int x, int y) {
	x = Find(x);
	y = Find(y);
	par[y] = x;
}

int main(void) {
	cin.tie(0);
	ios_base::sync_with_stdio(0);
	cin >> N >> M >> T;

	//루트 노드 초기화
	for (int i = 1; i <= N; i++) par[i] = i;

	while (T--) {
		int x;
		cin >> x;
		Union(0, x);
	}
	for (int i = 1; i <= M; i++) {
		int n, t;//파티원 수, 파티에서 말한 진실/거짓여부
		t = -1;
		cin >> n;
		for (int j = 1; j <= n; j++) {
			int x;
			cin >> x;
			party[i].push_back(x);//파티원 기록 -> 이후 정답 찾기
			if (!Find(x)) t = 0; //파티원중 한명이라도 진실을 아는 경우 t = 0
		}
		if (t != 0) t = Find(party[i][0]);
		for (int j = 0; j < n; j++) Union(t, party[i][j]);
	}
	//정답 찾기
	for (int i = 1; i <= M; i++) {
		int x = party[i][0];
		if (Find(x)) ans++;
	}
	cout << ans;
    return 0;
}

 

4. 정리

이 문제처럼 어떤 집합들을 만들고 대표하는 정보를 저장할 때 유니온 파인드를 사용하면 O(1)로 정보를 가져올 수 있습니다.