BOJ 15270 - 친구 팰린드롬

BOJ 15270 - 친구 팰린드롬

[ 분류 - 그래프 이론, 백트래킹 ]

출제하고 나서 시간이 꽤 지났지만, 역시 에디토리얼은 남겨야겠다고 생각해서 포스팅한다..

문제 조건을 정리하면 아래와 같다.

  1. A와 B가 춤을 추기로 되어 있다면 A는 B와 다른 친구와 춤을 출 수 없다.

  2. 모든 친구는 로봇 댄스를 출 수 있다.

 

단순 최대 매칭과 + 로봇 댄스로 무대에 올릴 수 있는 최대값을 정할 수 있다.

#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
const int MAX_V = 21;
vector<vector<int>> adj;
bool visit[MAX_V];
int N;
int go(int vn, int cnt) {
	if (vn == N) return cnt;
	if (visit[vn]) return  go(vn + 1, cnt);
	int res = 0;
	for (int to : adj[vn])
		if (!visit[to]) {
			visit[to] = 1;
			res = max(res, go(vn + 1, cnt + 1));
			visit[to] = 0;
		}
	return max(res, go(vn + 1, cnt));
}

int main() {
	int M, u, v;
	scanf("%d%d", &N, &M);
	adj = vector<vector<int>>(N);
	while (M--) {
		scanf("%d%d", &u, &v);
		u--, v--;
		if (u > v) swap(u, v);
		adj[u].push_back(v);
	}
	int res = go(0, 0);
	res *= 2; // 매칭은 두 정점이 이어졌다는 것.
	res = N > res ? (res + 1) : res; // 로봇댄스 출 친구 섭외
	printf("%d", res);
	return 0;
}