5 3
1 2
3 4
1 3

3

재귀를 사용한 백트래킹 기법으로 해결이 가능한 문제다.

먼저 입력에 맞춰서 섞으면 안되는 아이스크림을 bool타입 2차원 배열의 형태로 저장한다.

예를들어 1번과 3번 아이스크림을 섞어 먹을 수 없다면, cantMix[1][3] = true;, cantMix[3][1] = true; 와 같이 2차원배열에 저장해두고 1번 아이스크림부터 N번 아이스크림까지 반복문을 돌면서 고를 수 있는 아이스크림 3개를 골라 경우의 수를 카운팅하면 된다.

아이스크림을 고를 수 있는지 없는지 확인하기 위해 현재까지 고른 아이스크림을 저장하기 위한 배열을 별도로 만들고, 배열에 포함된 아이스크림들(현재까지 선택한 아이스크림들)과 고르고 싶은 아이스크림을 섞을 수 있는지 비교한 후 저장한다. 이 과정을 끝까지 반복하면 선택가능한 모든 경우의 수를 계산할 수 있다.

위 아이디어를 코드로 옮기면 아래와 같다.

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
int n,m,result = 0;
bool cantMix[201][201]; // 수의 범위가 작으므로 맵보다 배열이 유리
vector<int> selected;

/**
 * 같이 먹으면 안되는 아이스크림 조합 생성
 * 앞에서부터 아이스크림을 하나 고르고, 그 아이스크림과 함께 골라도 되는 경우만 세어서 3개 고를때까지 반복 => 숫자 세기
*/
// 몇개 골랐는지, 어떤 인덱스까지 탐색했는지(다음 인덱스부터 탐색)
void selectIce(int start){
    if(selected.size()==3){ // 3개를 골랐다면
        result++;
        return;
    }
    for(int i=start+1;i<n+1;i++){ // 1번부터 n번까지의 아이스크림에 대해
        // i번째 아이스크림을 현재 집합에 넣을 수 있는지 확인
        bool able = true; // 넣을 수 있음
        // 현재 집합에 포함된 수들과 합쳐서 넣어도 되는지 확인
        for(int j=0;j<selected.size();j++){
            if(cantMix[i][selected[j]]){ // i와 selected의 j번째 인덱스의 인자를 섞을 수 없다면
                able = false;
                break;
            }
        }
        if(able){ // 넣을수 있다면
            selected.push_back(i);
            selectIce(i);
            selected.pop_back();
        } 
    }
}


int main(){
    cin.tie(NULL) -> ios::sync_with_stdio(false);
    cin>>n>>m;
    int a,b;
    for(int i=0;i<m;i++){
        cin>>a>>b;
        // 섞어먹으면 안되는 조합들
        cantMix[a][b] = true;
        cantMix[b][a] = true;
    }
    selectIce(0); // 아이스크림 고르기
    cout<<result<<endl;
}

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

2 1
7

19

2 2
3 4

2

처음 문제를 접근했던 방식은 '선견지명'으로 알고 있는 숫자들을 미리 배치한 뒤, 남은 숫자들을 배치하는 것이었다.

하지만 위 방법으로 접근하게되면 알고리즘이 지나치게 복잡하게 된다는 단점이 있었고 생각을 단순화하여 수를 배치한 뒤 '선견지명'으로 알고있는 숫자들을 포함하는지 확인하는 방식으로 방향을 틀었다.

숫자들을 중복으로 포함할수 있기 때문에, '중복 순열'을 사용해야 하며 파이썬은 itertools의 product를 사용하여 이를 쉽게 구현 할 수 있다.

위 아이디어를 적용한 코드는 아래와 같다.

# https://www.acmicpc.net/problem/13908
from itertools import product  # 중복 순열
'''
중복 순열을 이용하여 만들 수 있는 모든 숫자를 만들어보고
만들어진 숫자가 '이미 알고 있는 수'를 포함한다면 result +=1
'''
result = 0
numbers = [i for i in range(10)]
n, m = map(int, input().split())
if m == 0:
    known = []
else:
    known = list(map(int, input().split()))  # 이미 알고 있는 수

for number_array in product(numbers, repeat=n):  # n개의 수 뽑기
    # 만들어진 수가 known을 모두 포함하는지 확인
    error = False
    for number in known:
        # 뽑은 숫자 배열에 known의 모든 수가 포함되어 있는지 확인
        if number not in number_array:  # 포함되어 있지 않다면
            error = True
            break
    if not error:  # 문제없이 known의 모든 수를 포함하였다면
        result += 1


print(result)

위 문제에서 주의해야 할 점은 m이 0으로 주어지는 경우, 알고있는 수에 대한 입력이 없다는 점이다. 

조건식을 통해 m이 0인 경우 빈 배열로 처리해야 하며, 수를 만든 이후, 수를 하나씩 비교하면서 '이미 알고있는 수'의 숫자가 모두 만들어진 수에 포함되는지 boolean 변수를 통해 확인하고 문제없다면 result를 +1 한다.

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