백준 알고리즘[1043]-거짓말

문제 사이트 : https://www.acmicpc.net/problem/1043

1043번: 거짓말

문제

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

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

입력

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

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

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

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

출력

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

 

 

접근 방법과 풀이

첫 번째 접근 방법은 무식하게 브루트 포스. 각 파티마다 거짓말을 한다/ 안 한다 로 나누고, 재귀 호출을 이용해 탐색을 했다. 만약 거짓말을 했을 때 진실을 아는 사람이 있다면, fail, 거짓말을 들키지 않고 파티를 모두 마쳤다면 maxLie 값을 갱신하면서 풀이해나갔다.

 

첫 번째 접근의 문제점은 시간이였다. 사실 문제의 의도를 착각하는바람에 애초에 알고리즘이 잘못되었지만, 당시에는 그 사실을 인지하지 못 하고 있었다. 그런데도 '틀렸습니다'가 아닌 '시간 초과'가 떠서 알고리즘은 맞는줄 착각하고 있었다.. 아무튼 시간복잡도를 계산하자면 위 알고리즘은 다음과 같은 결과가 나온다.

1. 각 파티에는 거짓말을 한다/안 한다 두 가지의 선택지가 있다.

2. 입력받을 수 있는 파티의 최대 개수는 50이다.

3. 각 파티는 2가지의 선택(거짓말을 할지 안할지의 여부)이 존재하니 재귀호출의 호출수는 대략 2 * 2^(M) - 1.

즉, 시간복잡도는 O(2^M)이라는 말도 안되는 수치가 나온다. 대충 M에 50을 대입하면 2^50은

1,125,899,906,842,624

이라는 어마어마한 값이 나온다.

 

두 번째 접근 방법은 결국 스스로 푸는 것을 포기하고 구글링을 했다. 그 결과 내가 문제를 잘못 이해하고있다는 충격적인 사실을 알았다.. 아까 문제에서 당연히, 어떤 사람이 어떤 파티에서는 진실을 듣고, 또다른 파티에서는 과장된 이야기를 들었을 때도 지민이는 거짓말쟁이로 알려지게 된다. 에서 착각을 했다.

1) 진실을 들은 후, 다음 파티에서 거짓말을 하면 들킴.

2) 거짓말을 들은 후, 다음 파티에서 진실을 말하면 괜찮음.

이라고 생각했던 것.. 하지만 위 문장에서는 진실을 들은 후,가 아니라 진실을 듣고,라는 것...

 

두 번째 의 접근 방법에서 문제를 이해했으니 다시 알고리즘을 짜기 시작했다. 알고리즘을 조금 공부한 사람은 이 문제를 보면 그래프의 연결..(뭔지 잘 모름)과 똑같은 문제임을 알 수 있다. 문제는 나는 그 알고리즘을 대략 알고있지만 어떻게 짜는지는 모른다. 암튼 내 방식대로 문제를 짜봤다.

 

+첫 시도에서 시간초과가 나왔다. 아무래도 나처럼 야매로 하면 안되나보다.. 사실 내가생각해도 극도로 비효율적이긴 했다. 두번째 시도에는 Queue를 이용해서 Queue에 진실을 알고있는 사람을 넣고, Queue에서 한 명씩 빼가며 탐색하고 Queue에서 Pop(뽑힌)된 사람은 다시 Queue에 쌓이지 않게 다른 arr에 tag를 하는 식으로 진행했다.

이렇게하니 시간초과도 안걸리고 잘 풀렸다.

 

코드

깃허브 : https://github.com/daily-boj/yoonki1207/blob/master/P1043.cpp 깃헙에 올라와있는건 살짝 지저분함..

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<stdio.h>
#include<vector>
#include<queue>
using namespace std;
#define FOR(i, n) for(int i = 0 ; i < n ; i++)
#define MAXX 987654321

int partyCome[50][50];
int knowTruth[50];
queue<int> vTruth;
int N, M;
int maxLie = 0;

void solve() {
	while(!vTruth.empty()){
		int k = vTruth.front();
		knowTruth[k] = -1;
		vTruth.pop();
		for (int m = 0; m < M; m++) {
			if (partyCome[m][k]!=0) {
				partyCome[m][k] = -1;
				for (int n = 0; n < N; n++) {
					if (partyCome[m][n]!=0) {
						partyCome[m][n] = -1;
						if (knowTruth[n] != 1 && knowTruth[n] != -1)
							vTruth.push(n);
						knowTruth[n] = 1;
					}
				}
			}
		}
	}
}

int main() {
	scanf("%d %d", &N, &M);
	int kT;
	scanf("%d", &kT);
	FOR(i, kT) {
		int n;
		scanf("%d", &n);
		knowTruth[n - 1] = 1;
		vTruth.push(n - 1);
	}
	for (int i = 0; i < M; i++) {
		int numP;
		scanf("%d", &numP);
		if (numP == 0)
			maxLie--;
		for (int j = 0; j < numP; j++) {
			int n;
			scanf("%d", &n);
			partyCome[i][n - 1] = 1;
		}
	}
	/*printf("BEFORE\n");
	for (int i = 0; i < M; i++, printf("\n"))
		for (int j = 0; j < N; j++)
			printf("%d ", partyCome[i][j]);*/
	solve();
	/*printf("AFTER\n");
	for (int i = 0; i < M; i++, printf("\n"))
		for (int j = 0; j < N; j++)
			printf("%d ", partyCome[i][j]);
	printf("TRUE PARTY\n");*/
	for (int i = 0; i < M; i++)
		if (trueParty[i] == 0)
			maxLie++;
	printf("%d\n", maxLie);
}