[백준] 2422 한윤정이 이탈리아에 가서 아이스크림을 사먹는데

https://www.acmicpc.net/problem/2422

2422번: 한윤정이 이탈리아에 가서 아이스크림을 사먹는데

#include <iostream>
#include <vector>
#include <map>
using namespace std;
	
int n, m;
int answer; 
int arr[210];
int choice[5];
bool visit[210];

vector <int> cant[210];

bool checker(int cnt, int new_no) {

	if(cnt == 0)
		return true;

	for(int i=0; i<cant[new_no].size(); i++) {
		int a = cant[new_no][i];
		if(cnt == 1) {
			if(choice[0] == a)
				return false;
		}
		else if(cnt == 2) {
			if(choice[0] == a || choice[1] == a)
				return false;
		}

	}
	return true;


void dfs(int cnt, int idx, int target) {
	if(cnt == target) {	
		answer++;
		return;
	}

	for(int i=idx; i<=n; i++) {
		if(visit[i]) continue;
		if(checker(cnt, arr[i]) == false)
			continue;
		visit[i] = true;
		choice[cnt] = arr[i];
		dfs(cnt+1, i, target);
		visit[i] = false;
		choice[cnt] = 0;
	}
}

int main() {

	scanf("%d %d", &n, &m);

	for(int i=1; i<=n; i++) {
		arr[i] = i;
	}

	for(int i=0; i<m; i++) {
		int a, b;
		scanf("%d %d", &a, &b);
		cant[a].push_back(b);
		cant[b].push_back(a);
	}


	dfs(0, 1, 3);


	printf("%d\n", answer);



	return 0;
}

모든 조합을 다 구한 후에 검증을 하면 시간초과가 난다.

따라서, 각 노드를 추가할때마다 넣어도 되는 노드인지 검증한다.

검증하는 과정에서 매번 모든 섞어먹으면 안 되는 조합을 탐색하여 검증하여 시간초과가 났다. (이럴 경우, 무관한 조합또한 확인해버림)

따라서 vector <int> cant[아이스크림번호] 를 사용하여 "아이스크림번호" 와 함께할수없는 경우만 탐색하여 검증과정을 거치는 식으로 하여 시간초과를 피했다.