백준 2016번 미팅 주선하기 C++

출처 : https://www.acmicpc.net/problem/2016

 

문제에 쓰여있는 대로 구현을 했는데 구현하는데 시간이 꽤 걸렸다. 생각보다 까다로웠던 문제였다.

 

#include <iostream>
#include <string>
#include <vector>
#include <math.h>
#include <algorithm>
#include <utility>
#include <stack>
#include <queue>
#include <math.h>
#include <set>
#include <map>
#include <unordered_map>
#include <unordered_set>

using namespace std;
using ll = long long;

vector<vector<int>> v(11, vector<int>(5));
vector<bool> visited(11, false);
vector<int> th;
int origin_match = 0;
int match_max = 100;

void Solve() {
	bool isOrigin = true;
	for (int i = 0; i < 5; i++) {
		v[1][i] = th[i];
		if (th[i] != i + 6) isOrigin = false;
	}
	vector<vector<int>> tjj(11, vector<int>());
	vector<int> proposed(6, 0);
	vector<bool> tjjed(11, true);

	while (true) {
		for (int i = 6; i <= 10; i++) {
			for (int j = 0; j < 5; j++) {
				if (!tjjed[i]) break;
				int boy = v[i][j];
				if (find(tjj[boy].begin(), tjj[boy].end(), i) != tjj[boy].end()) continue;
				if (proposed[boy] == 0) {
					proposed[boy] = i;
					tjjed[i] = false;
				}
				else {
					auto currIt = find(v[boy].begin(), v[boy].end(), proposed[boy]);
					auto newIt = find(v[boy].begin(), v[boy].end(), i);
					if (currIt > newIt) {
						tjj[boy].push_back(proposed[boy]);
						tjjed[i] = false;
						tjjed[proposed[boy]] = true;
						proposed[boy] = i;
					}
					else {
						tjj[boy].push_back(i);
					}
				}
				break;
			}
		}
		bool isBreak = true;
		for (int i = 6; i <= 10; i++) {
			if (tjjed[i]) isBreak = false;
		}
		if (isBreak) break;
	}
	if (isOrigin) origin_match = proposed[1];
	else match_max = min(match_max, proposed[1]);
}

void BT(int cnt) {
	if (cnt >= 5) {
		Solve();
		return;
	}
	for (int i = 6; i <= 10; i++) {
		if (!visited[i]) {
			th.push_back(i);
			visited[i] = true;
			BT(cnt + 1);
			th.pop_back();
			visited[i] = false;
		}	
	}
}

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

	int t;
	cin >> t;
	while (t--) {
		for (int i = 2; i <= 10; i++) {
			for (int j = 0; j < 5; j++) {
				cin >> v[i][j];
			}
		}
		BT(0);
		if (match_max < origin_match) cout << "YES" << "\n";
		else cout << "NO" << "\n";
		origin_match = 0;
		match_max = 100;
		th.clear();
	}
};