[C++] 순열과 조합 DFS로 구현해보기

코딩 테스트를 준비하면서 느낀건데 최종 보스는 DFS와 dp인 것 같다. 생각하기는 어려운데 굉장히 직관적이랄까.. 백준 문제를 풀다가 조합이 꼭 필요한 문제가 있었는데 조합을 구현할 줄 몰라서 이 글을 쓰게 됐다. 조합을 먼저 구현한 뒤에 순열을 구현해 보겠다. 둘 다 재귀를 이용한 DFS로 구현한다.

​

​

1. 조합

그냥 직관적으로 생각해보자. 크기가 5인 배열 {4, 2, 1, 3, 5}에서 3개를 뽑는 5_C_3의 경우를 예로 들어보자. 첫번째 숫자부터 차례대로 뽑았다가 3개를 다 뽑으면 다시 되돌아오고 다음 숫자를 뽑을 것이다. 말로 하면 헷갈리니 그림으로 보자. 5가지 경우의 수까지를 살펴보면 아래와 같다.

 

우선 조합에서는 각 경우의 수 마다 '한 번 뽑으면 다시 쳐다볼 필요가 없다'가 중요하다. 그래서 두 개의 배열을 사용한다. select 배열에는 방문 여부를 나타내고, map 배열은 뽑으려는 숫자 배열이다. 공을 뽑았는지 여부는 select 배열을 통해 알 수 있고, 뽑은 숫자는 map 배열을 통해 알 수 있다.

 

void DFS(int select[], int map[], int idx, int cnt, int n, int k)

 

함수의 형태는 위와 같고, 아래는 파라미터에 대한 설명이다.

 

select 배열 → 공 뽑았는지 여부(0이면 안뽑음, 1이면 뽑음)

map 배열 → 숫자 배열

idx → 뽑는 숫자의 인덱스

cnt → 현재까지 뽑은 숫자 개수

n, k → n_C_k의 n, k

​

idx의 역할은 화살표가 오른쪽 방향으로만 향하게 하는 것이다. 이게 핵심이다. 아래 코드를 보면 알겠지만 for 문은 idx를 시작으로 끝까지 반복된다. 공을 뽑을 때 4 → 2 → 1 순서로 뽑는 것과 4 → 1 → 2 순서로 뽑는 것은 조합에서는 같은 것으로 치기 때문이다. 이 예시는 순열을 설명할 때 다시 쓰니깐 기억하도록 하자.

​

select 배열은 '중복 방지' 역할을 하기도 한다. select 배열이 없으면 공을 뽑았는지 안뽑았는지 모르기 때문에 중복해서 뽑을 수 있는 문제가 있다. 이게 여기서만 문제지 중복 조합에서는 해결책이다.

​

다시 그림으로 돌아가자. 우선 재귀함수니깐 종료 조건이 필요하다. 종료 조건은 'cnt == k'임을 쉽게 알 수 있다. 아직 종료되지 않았다면? idx를 기준으로 배열의 끝까지 for문으로 탐색하면서 뽑아주면 된다. select 배열에서 idx번째 공이 이미 뽑혔으면 continue로 턴을 무효화시키고, 아직 뽑지 않았으면 뽑고 → 재귀를 돌리고 → 다시 무효화시켜줘야 한다. 다시 무효화시키는 부분이 약간 헷갈리는데, 그림에서 화살표가 돌아가는 것으로 이해하면 된다.

 

#include <iostream>
using namespace std;

void print(int select[], int map[], int size){
    for(int i = 0; i < size; i++){
        if(select[i] == 1)
            cout << map[i] << " ";
    }
    cout << endl;
}

void DFS(int select[], int map[], int idx, int cnt, int n, int k){
    if(cnt == k){
        print(select, map, n);
        return;
    }
    
    for(int i = idx; i < n; i++){
        if(select[i] == 1) continue;
        select[i] = 1;
        DFS(select, map, i, cnt + 1, n, k);
        select[i] = 0;
    }
}

int main(){
    
    int select[5] = {0,};
    int map[5] = {4,2,1,3,5};
    
    int n = 5, k = 3; // 5_C_3
    
    DFS(select, map, 0, 0, n, k);
    
    return 0;
}

 

 

2. 중복 조합

중복 조합은 말 그대로 '중복을 허용하는 조합'을 말한다. 배열 {4,2,1,3,5}에서 [4,4,4], [4,4,2], [4,4,1]과 같이 뽑을 수 있다는 뜻이다. 핵심은 select 배열에 있다. 조합에서는 중복으로 뽑으면 안되기 때문에 select 배열을 만들어 줬었다. 그런데 중복 조합에서는 중복을 허용하기 때문에 select 배열이 필요 없다. 단, 화살표가 우측으로만 가야 하므로 idx 변수는 필요하다. 그냥 벡터 하나를 선언해준 다음에 push, pop만 해주면 된다. 출력은 벡터만 출력한다.

 

#include <iostream>
#include <vector>
using namespace std;

void print(vector<int> v){
    for(int elem : v)
        cout << elem << " ";
    cout << endl;
}

void DFS(int map[], int idx, int cnt, int n, int k, vector<int> v){
    if(cnt == k){
        print(v);
        return;
    }
    
    for(int i = idx; i < n; i++){
        v.push_back(map[i]);
        DFS(map, i, cnt + 1, n, k, v);
        v.pop_back();
    }
}

int main(){
    
    int map[5] = {1,2,3,4,5};
    
    int n = 5, k = 3; // 5_C_3
    vector<int> v;
    
    DFS(map, 0, 0, n, k, v);
    
    return 0;
}

 

 

3. 순열

순열과 조합의 차이점은 무엇일까? 순열은 순서를 고려한다. 따라서 공을 뽑을 때 화살표가 뒤로 돌아갈 수 있다. 아래 그림을 보자.

순열과 조합의 차이점 : 순열은 뒤로 돌아갈 수 있다

 

조합에서는 위 두 경우를 같은 것으로 친다. 하지만 순열은 다르다. 화살표가 뒤로 돌아갈 수 있다. 조합에서 화살표가 오른쪽으로만 향하게 하는 역할은 idx 변수가 한다고 했었다. 순열은 화살표가 뒤로 갈 수 있기 때문에 idx 변수가 필요 없다. 따라서 for 문도 i = 0을 기준으로 한다. 그러면 아래와 같이 바꾸면 될까?

 

void DFS(int select[], int map[], int cnt, int n, int k){
    if(cnt == k){
        print(select, map, n);
        return;
    }
    
    for(int i = 0; i < n; i++){
        if(select[i] == 1) continue;
        select[i] = 1;
        DFS(select, map, cnt + 1, n, k);
        select[i] = 0;
    }
}

 

위 코드는 조합 코드에서 idx만 지운 코드다. 이렇게 하면 어떤 문제가 발생할까? 우선 for문에서 i = 0부터 시작하니깐 화살표가 뒤로 갈 수는 있게 됐다. 그런데 출력시 순서에 문제가 발생한다. print() 함수를 살펴보자.

 

void print(int select[], int map[], int size){
    for(int i = 0; i < size; i++){
        if(select[i] == 1)
            cout << map[i] << " ";
    }
    cout << endl;
}

 

select의 인덱스를 순서대로 순회하면서 값이 1인 인덱스를 map과 매핑시켜 숫자를 출력해주는 방식이다. 공을 뽑을 때 4 → 2 → 1 순서로 뽑는 것과 4 → 1 → 2 순서로 뽑는 경우 모두 select는 {1,1,1,0,0}이 된다. 따라서 뽑은 순서는 다르지만 print() 함수에 의해 둘 다 '4 → 2 → 1'로 출력된다. 이를 해결하는 방법은 벡터를 생성해서 공을 뽑을때마다 push해주고, 무효화시킬때 pop해주면 된다. 대신 출력은 그냥 벡터를 출력하면 된다. 코드는 아래와 같다.

 

#include <iostream>
#include <vector>
using namespace std;

void print(vector<int> v){
    for(int elem : v)
        cout << elem << " ";
    cout << endl;
}

void DFS(int select[], int map[], int cnt, int n, int k, vector<int> v){
    if(cnt == k){
        print(v);
        return;
    }
    
    for(int i = 0; i < n; i++){
        if(select[i] == 1) continue;
        select[i] = 1;
        v.push_back(map[i]);
        DFS(select, map, cnt + 1, n, k, v);
        v.pop_back();
        select[i] = 0;
    }
}

int main(){
    
    int select[5] = {0,};
    int map[5] = {4,2,1,3,5};
    vector<int> v;
    
    int n = 5, k = 3; // 5_P_3
    
    DFS(select, map, 0, n, k, v);
    
    return 0;
}

 

 

4. 중복 순열

중복 순열은 조합, 중복 조합, 순열을 이해했다면 설명할 게 없다. 순열 코드에서 select 배열을 지워주기만 하면 된다. 화살표의 방향이 뒤로 갈 수 있기 때문에 idx는 필요 없다. 중복 조합에서 idx가 없다는 점만 다르고 나머지는 똑같다.

 

#include <iostream>
#include <vector>
using namespace std;

void print(vector<int> v){
    for(int elem : v)
        cout << elem << " ";
    cout << endl;
}

void DFS(int map[], int cnt, int n, int k, vector<int> v){
    if(cnt == k){
        print(v);
        return;
    }
    
    for(int i = 0; i < n; i++){
        v.push_back(map[i]);
        DFS(map, cnt + 1, n, k, v);
        v.pop_back();
    }
}

int main(){
    
    int map[5] = {1,2,3,4,5};
    vector<int> v;
    
    int n = 5, k = 3; // 5_P_3
    
    DFS(map, 0, n, k, v);
    
    return 0;
}