[백준 19541] 역학 조사

문제 링크 => 19541번: 역학 조사 (acmicpc.net)

19541번: 역학 조사

---

Greedy 알고리즘 문제이다.

 

이 문제는 시간순으로 모임의 정보가 주어져 있으며 전염된 결과를 제공해주기 때문에 역으로 접근하여 문제를 해결하면 풀리는 문제이다.

 

즉, 역순으로 해당 그룹에 있는사람들의 전염된 결과를 확인하고 모든 사람들이 전염된 경우와 한 사람이라도 전염되지 않은 경우 두 케이스를 나눠서 보는게 중요하다.

 

1. 모든 사람들이 전염된 경우 => Pass

 

2. 한 사람이라도 전염되지 않은 경우 => 이 경우가 중요한데 그룹에 존재하는 사람들이 한번 참여했는지 or 두번 이상 참여했는지의 여부에 따라서 다르게 판단해줘야 한다.

 

즉, 여러번 참여한 경우를 판단하기 위에 Map 자료구조를 사용하였고 이 경우 또한 두가지 케이스로 분류할 수 있다.

 

2-1. 그룹에 존재하는 사람들 중 한명이 한번만 참여한 경우 =>  이 경우 해당 사람이 전염된 경우에는 존재할 수 없는 케이스다. 그 이유를 다음과 같은 예시로 확인해본다.

 

ex) 5 6 7 / 1 0 1 에서 5, 6, 7 사람이 전부 처음으로 그룹에 참여했다고 가정하자.

 

한 사람이 전염되지 않은 경우이므로 나머지 5, 7번 사람은 전염되지 않은 경우가 되거나 6번 사람은 그대로 냅두면 된다. 

 

5, 7번 사람이 감염되지 않게 할 경우 감염된 결과와 다른 결과를 내기 때문에 이 경우는 모순이다.

 

즉, 그룹 내에 모든 사람들이 그룹에 처음으로 참여한 경우 모두 전염이 되거나 아니거나 둘 중 하나가 되어야 한다.

 

그러므로 그룹에 한번만 참여한 사람들은 감염된 경우에 판단할 수 없는 경우가 된다.

 

그렇다면 위 경우를 판별해내기 위해서 어떻게 해야할까? 

=> 판별하기 위해서 그룹에 존재하는 사람들 중 한명이 두번 이상 참여한 사람들이 전염된 경우 전염되지 않은 경우로 변경만 하면 그만이다.

 

2-2. 그룹에 존재하는 사람들 중 한명이 두번 이상 참여한 경우 => 이 경우 해당 사람이 해당 그룹에서 전염되지 않았을수도 있으므로 전염되지 않았다고 변경해준다.

 

ex) 1 2 3 / 0 0 1 에서 1, 2번 사람은 처음으로 그룹에 참여하고 3번 사람이 2번 이상 그룹에 참여했다고 가정하자.

 

이 경우 1, 2번 사람은 전염되지 않았으므로 모순이 아니며 3번 사람은 전염되었으므로 이 전염되지 않았다고 변경해주면 된다.

 

즉, 해당 그룹에 한사람이라도 전염되면 모든 사람들이 전염이 되야 하는데 이러한 경우에는 2번 이상 그룹에 참여한 사람들이 해당 그룹에서는 전염되지 않았다는 것을 의미하며 1번만 그룹에 참여한 사람들은 무조건 전염되지 않은 경우여야 하며 전염된 경우는 모순이다.

 

풀이 code

#define _CRT_SECURE_NO_WARNINGS
#include <string>
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <queue>
#include <stack>
#include <time.h>
#define INF 100000000
#define endl '\n'
#define ll long long

using namespace std;

int N, M;
vector<int> v[100001];
int arr[100001];
map<int, int> m;
string result = "YES";

void solve() {
	for (int i = M - 1; i >= 0; i--) {
		int op = 0;
		for (int j = 0; j < v[i].size(); j++) {
			if (arr[v[i][j]]) op++;
			m[v[i][j]]++;
		}
		if (op != v[i].size()) {
			for (int j = 0; j < v[i].size(); j++) {
				if (m[v[i][j]] == 1) {
					if (arr[v[i][j]] == 1) {
						result = "NO";
						return;
					}
				}
				else {
					if (arr[v[i][j]] == 1) {
						arr[v[i][j]] = 0;
					}
				}
			}
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);

	cin >> N >> M;
	for (int i = 0; i < M; i++) {
		int k;
		cin >> k;
		for (int j = 0; j < k; j++) {
			int x;
			cin >> x;
			v[i].push_back(x);
		}
	}
	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
	}

	solve();

	cout << result << endl;
	if(result=="YES") for (int i = 1; i <= N; i++) cout << arr[i] << " ";

	return 0;
}