[단계별로 풀어보기] 백트래킹

1. N과 M(1)

#include <iostream>
#include <vector>
#include <cstring>
#include <string>

using namespace std;
int m, n;
int path[10] = { 0 };
int used[10] = { 0 };

void run(int le) {

    if (le == m) {
        for (int i = 0; i < le; i++) {
            cout << path[i] << " ";
        }
        cout << "\n";
    }

    for (int x = 0; x < n; x++) {
        if (used[x] != 0) continue;
        used[x] = 1;
        path[le] = x + 1;
        run(le + 1);
        used[x] = 0;
        path[le] = 0;
    }
}

int main() {
    cin >> n >> m;

    run(0);
    return 0;
    
}

1. N과 M(2)

#include <iostream>
#include <vector>
#include <cstring>
#include <string>

using namespace std;
int m, n;
int path[10] = { 0 };
int used[10] = { 0 };

void run(int le, int s) {

    if (le == m) {
        for (int i = 0; i < le; i++) {
            cout << path[i] << " ";
        }
        cout << "\n";
    }

    for (int x = s; x < n; x++) {
        if (used[x] != 0)continue;
        used[x] = 1;
        path[le] = x + 1;
        run(le + 1, x+1); //s+1이아닌 x+1
        used[x] = 0;
        path[le] = 0;
    }
}

int main() {
    cin >> n >> m;

    run(0, 0);
    return 0;
    
}

3. N과 M(3)

#include <iostream>
#include <vector>
#include <cstring>
#include <string>

using namespace std;
int m, n;
int path[10] = { 0 };

void run(int le) {

    if (le == m) {
        for (int i = 0; i < m; i++) {
            cout << path[i] << " ";
        }
        cout << "\n";
        return;
    }

    for (int x = 0; x < n; x++) {
        path[le] = x + 1;
        run(le + 1); 
        path[le] = 0;
    }
}

int main() {
    cin >> n >> m;

    run(0);
    return 0;
    
}

4. N과 M(4)

#include <iostream>
#include <vector>
#include <cstring>
#include <string>

using namespace std;
int m, n;
int path[10] = { 0 };

void run(int le, int s) {

    if (le == m) {
        for (int i = 0; i < m; i++) {
            
            cout << path[i] << " ";
        }
        cout << "\n";
        return;
    }

    for (int x = s; x < n; x++) {
        path[le] = x + 1;
        run(le + 1, x); 
        path[le] = 0;
    }
}

int main() {
    cin >> n >> m;

    run(0, 0);
    return 0;
    
}

5. N-Queen

- Test1. 정답은 맞는데 시간초과..

#include <iostream>
#include <vector>
#include <cstring>
#include <string>

using namespace std;
int n;
int path[20] = { 0 };
int used[20] = { 0 };

//예를 들어(0, 1)을 기준으로 했을때,
//대각선에 있는 점(1, 2) 은(0 - 1) = (1 - 2) = -1 을 만족하며
//대각선에 있는 점(2, 3) 은(0 - 2) = (1 - 3) = -2 를 만족한다.


int cnt = 0;

int abs(int v) {
    if (v < 0) return -v;
    else return v;
}

void check() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j)continue;
            if (abs(path[i] - path[j]) == abs(i - j)) return;
            if (i == n - 1) {
                /*for (int q = 0; q < n; q++)
                    cout << path[q];
                cout << endl;*/
                cnt++;
                return;
            }
        }
    }
}

void run(int le) {

    if (n == 1) {
        cnt++;
            return;
    }


    if (le == n) {
        check();
        return;
    }

    for(int x = 0; x < n; x++) {
        if (used[x] != 0) continue;
        used[x] = 1;
        path[le] = x;
        run(le + 1);
        used[x] = 0;
        path[le] = 0;
    }

}

int main() {
    cin >> n;
    
    run(0);

    cout << cnt;

    return 0;    
}

- Test2. 이중반복문 사용하지 않고 조건문 활용하기

#include <iostream>
#include <vector>
#include <cstring>
#include <string>

using namespace std;
int n;
int path[20] = { 0 };

//예를 들어(0, 1)을 기준으로 했을때,
//대각선에 있는 점(1, 2) 은(0 - 1) = (1 - 2) = -1 을 만족하며
//대각선에 있는 점(2, 3) 은(0 - 2) = (1 - 3) = -2 를 만족한다.


int cnt = 0;

int abs(int v) {
    if (v < 0) return -v;
    else return v;
}

bool check(int le) { // 같은행에 있을수는 없음
    for (int i = 0; i < le; i++) {
             //이전퀸의 같은 열 || 이전퀸과의 위치차의 절댓값이 같으면 대각선 
        if (path[le] == path[i] || le - i == abs(path[le] - path[i]))
            return false;
    }


    return true;
}

//le = 행, path[le]=해당 행의 퀸 위치
void run(int le) {

    if (n == 1) {
        cnt++;
        return;
    }


    if (le == n) {
        cnt++;

        /*for (int q = 0; q < n; q++)
            cout << path[q];
        cout << endl;*/

        return;
    }

    for (int x = 0; x < n; x++) {
        path[le] = x;
        if (check(le)) //해당행의 배치가 가능하면 재귀 -> 시간복잡도 줄임
            run(le + 1);
    }

}

int main() {
    cin >> n;

    run(0);

    cout << cnt;

    return 0;
}

7. 연산자 끼워넣기

#include <iostream>
#include <vector>
#include <cstring>
#include <string>

using namespace std;

int n;
int num[12] = { 0 };
int p, m, mu, di;
vector <char>cal;
char path[12];
int used[12];
int mmax = -21e8;
int mmin = 21e8;

void run(int le) {
    if (le == n - 1) {
        int result = num[0];
        for (int x = 0; x < le; x++) {
            if (path[x] == 'p')
                result += num[x + 1];
            else if (path[x] == 'm')
                result -= num[x + 1];
            else if(path[x]=='M')
                result *= num[x + 1];
            else if (path[x] == 'D')
                result /= num[x + 1];
        }
        if (result > mmax) mmax = result;
        if (result < mmin) mmin = result;
    }
    
    for (int i = 0; i < n - 1; i++) {
        if (used[i] != 0)continue;
        used[i] = 1;
        path[le] = cal[i];
        run(le + 1);
        used[i] = 0;
        path[le] = '\0';
    }
}

int main() {

    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> num[i];

    cin >> p >> m >> mu >> di;
    
    for (int i = 0; i < p; i++) {
        cal.push_back('p');
    }
    for (int i = 0; i < m; i++) {
        cal.push_back('m');
    }
    for (int i = 0; i < mu; i++) {
        cal.push_back('M');
    }
    for (int i = 0; i < di; i++) {
        cal.push_back('D');
    }

    run(0);

    cout << mmax << '\n' << mmin;

    return 0;    
}