[CodeForces] 1230C - Anadi and Domino

문제 : https://codeforces.com/contest/1230/problem/C

---

[알고리즘풀이]

전체 경우의 수가 적기 때문에, BackTracking을 이용해서 문제를 풀 수 있다.

Graph가 주어졌을 때, BackTracking을 이용해 그래프의 노드마다 1 ~ 6 중 번호를 부여하고,

모든 경우의 수에 대해서 Edge 마다 연결된 노드의 번호에 해당하는 주사위를 배정해준다.

N이 많아야 7이므로 모든 경우의 수를 탐색해도 6^7 번만 탐색하면 된다.

#include<iostream>
#include<vector>
#include<algorithm>

using namespace std;

int n, m, x, y, ans = -1;
int map[8][8];
bool check[7][7];

void bt(vector<int> v);

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> x >> y;
		map[x][y] = 1, map[y][x] = 1;
	}
	for (int i = 1; i <= 6; i++) {
		vector<int> v;
		v.push_back(i);
		bt(v);
		v.pop_back();
	}
	cout << ans;
	return 0;
}

void bt(vector<int> v) {
	if (v.size() == n) {
		for (int i = 1; i <= 6; i++)
			for (int j = 1; j <= 6; j++)
				check[i][j] = false;
		int c = 0;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (map[i][j] == 1) {
					int A = min(v[i - 1], v[j - 1]);
					int B = max(v[i - 1], v[j - 1]);
					if (check[A][B] == false) {
						check[A][B] = true;
						c++;
					}
				}
			}
		}
		if (c > ans)
			ans = c;
		return;
	}
	for (int i = 1; i <= 6; i++) {
		v.push_back(i);
		bt(v);
		v.pop_back();
	}
}

---