BOJ 1043

27 Jan 2020 • ProblemSolving

거짓말

문제출처

1.설계(X)

  • 문제 해석

    • 사람수 N과 그 이야기의 진실을 아는 사람이 주어지고, 각 파티에 오는 사람들의 번호가 주어집니다.
    • 거짓말쟁이로 알려지지 않으면서, 과정된 이야기를 할 수 있는 파티개수의 최댓값을 구하는 문제입니다.

  • 설계

    • 문제를 이해하기 어려웠고, 아이디어를 찾지 못해 baarkingDog님의 구현을 참조하였습니다.
    • 각 파티에서 어떤사람들이 같이 파티를 하는 지 edge를 설정합니다.
    • 진실을 아는 사람들을 큐에 넣어 해당 edge와 연결되는 모든 구성원들을 진실을 알게 합니다.
    • 진실을 모두 모르는 파티를 카운트해 출력하게 됩니다.

2.구현(X)

  • 코드
#include <iostream>
#include <vector>
#include <queue>
#define MAXN 51
using namespace std;


bool know[MAXN];

vector<int> party[MAXN];
queue<int> q;
int arr[MAXN][MAXN];
int N, M;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M;
	int tmp;
	cin >> tmp;
	for (int i = 0 ;i <tmp; i++){
		int idx;
		cin >> idx;
		know[idx] = true;
		q.push(idx);
	}
	for (int i = 0; i < M; i++) {
		int num;
		cin >> num;
		for (int j = 0; j < num; j++) {
			int idx;
			cin >> idx;
			party[i].push_back(idx);
		}
		for (int j = 0; j < num; j++) {
			for (int k = j + 1; k < num; k++) {
				arr[party[i][j]][party[i][k]] = 1;
				arr[party[i][k]][party[i][j]] = 1;
			}
		}
	}
	while (!q.empty()) {
		int idx = q.front();
		q.pop();
		for (int i = 1; i <= N; i++) {
			if (arr[idx][i] && !know[i]) {
				know[i] = true;
				q.push(i);
			}
		}
	}
	
	int ans = 0;
	for (int i = 0; i < M; i++) {
		bool flag = false;
		for (int j = 0; j < party[i].size(); j++) {
			if (know[party[i][j]]) {
				flag = true;
				break;
			}
		}
		if (!flag) ans++;
	}
	cout << ans << "\n";
	return 0;
}

  • 디버깅

  • 제출결과

3.마무리

  • 테스트 케이스가 부실하여 예외케이스를 생각하기 어려웠고, 문제 자체를 이해하는데 시간이 오래걸렸습니다. 아이디어를 생각하는 것이 어려웠으나, 구현은 어렵지 않았습니다.
 BOJ

Related Posts