백준 2422 한윤정이 이탈리아에 가서 아이스크림을

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

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

 

#define NSIZE 201
#define MSIZE 10000
#include<stdio.h>
#include<iostream>
#include<vector>
using namespace std;
int N, M;
vector<int>num;
int chkNUM[NSIZE][NSIZE];
void init() {
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int a, b;
        cin >> a >> b;
        chkNUM[a][b] = chkNUM[b][a] = 1;
    }
}
bool chk(int num1) {
    for (int i = 0; i < num.size(); i++) {
        if (chkNUM[num[i]][num1] == 1 ||
            chkNUM[num1][num[i]] == 1)return false;
    }
    return true;
}
int ret = 0;
 
void dfs1(int cnt) {
    if (num.size() == 3) {
        ret++;
        return;
    }
    for (int i = cnt; i <= N; i++) {
        if (chk(i)) {
            num.push_back(i);
            dfs1(i + 1);
            num.pop_back();
        }
 
    }
}
int main(void) {
    init();
    dfs1(1);
    cout << ret << endl;
    return 0;
}

위의 설명을 코드로 옮긴것입니다.

 

그래프 같이 저장하는것은

 

이렇게 하시면됩니다. 정말 간단하지 않나요? 이문제는 조합을 만드는것은 여러가지 방법이있지만 그것에서 시간초과가 안생기므로 chk해주는 함수를 잘 짜도록 해봅시다. 여기서 저도 실수 했거든요.