[백트랙킹]백준15663번 N과 M(9)

백준15663번

백트랙킹을 연습해 볼 수 있는 문제 시리즈인 N과 M의 9번째 유형이다.

다른 문제들과 다른 점은 주어지는 자연수에 중복이 있다는 것이다.

자연수에 중복이 있는 경우를 고려하여 수열을 출력해야 한다면 어떻게 처리해야 할 지 감이 잘 오지 않았다.

다만, 문제에서 주어진 조건 중에 수열은 사전 순으로 증가하는 순서로 출력해야 한다는 말이 있었기에 가능한 방법이 한가지 있다.

바로 직전에 출력한 숫자를 다시 출력하지 않도록 하는 것이다.

문제에서 주어진 예제 중 두 번째를 보면 백트랙킹으로 첫 번째 자리를 선택한 상태에서 두 번째 자리를 고르는 for문으로 들어왔을 것이기 때문에, 여러 개의 숫자가 중복되어 있다면 같은 자리에서는 같은 숫자를 뽑지 않도록 하면된다.

주어진 자연수들을 사전 순으로 미리 정렬해놓는다면 중복되는 숫자들은 연이어서 선택될 것이기 때문에 이번에 뽑으려는 숫자가 현재 자리수에서 직전에 골랐던 숫자와 같은 경우는 선택하지 않도록 하면 중복되는 수열을 출력하지 않을 수 있다.

void btk(int n){
    if(n==M){
        for(int i=0;i<M;i++){
            cout << arr[i] << " ";
        }
        cout << "\n";
        return;
    }
    int lastNum = -1;
    for(int i=0;i<N;i++){
        if(!isUsed[i] && lastNum != arr2[i]){
            isUsed[i] = true;
            arr[n] = arr2[i];
            lastNum = arr2[i];
            btk(n+1);
            isUsed[i] = false;
        }
    }
}

lastNum 변수를 백트랙킹 함수 내에 선언해주었다. 전역 변수로 선언하지 않은 이유는 각 자리수마다 따로 처리를 해주어야 하기 때문이다.

예를 들어, 전역 변수로 놓았을 경우 문제에서 주어진 예제 2의 경우 9 9 를 출력할 수 없게 된다.

때문에 각 자리수로 들어올 때 마다 직전에 뽑았던 숫자를 따로 처리해주는 것이 바람직하다.

이번에 뽑은 숫자가 직전에 뽑은 숫자와 같지 않다면 백트랙킹을 진행하게 된다.

숫자를 뽑는 경우에는 직전에 선택한 숫자를 업데이트한다.

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

int N,M;
int arr[8];
vector<int> arr2;
int isCount[10001];
//bool isUsed[10001];
bool isUsed[8];
void btk(int n){
    if(n==M){
        for(int i=0;i<M;i++){
            cout << arr[i] << " ";
        }
        cout << "\n";
        return;
    }
    int lastNum = -1;
    for(int i=0;i<N;i++){
        if(!isUsed[i] && lastNum != arr2[i]){
            isUsed[i] = true;
            arr[n] = arr2[i];
            lastNum = arr2[i];
            btk(n+1);
            isUsed[i] = false;
        }
    }
}

int main(){
    cin >> N >> M;
    
    for(int i = 0;i<N;i++){
        int tmp;
        cin >> tmp;
        arr2.push_back(tmp);
    }
    sort(arr2.begin(),arr2.end());
    btk(0);
}