BOJ 백준 15649: N과 M (1)

Table of contents

들어가며

$n P m$ 개수 만큼의 순열을 구해서 출력하는 문제입니다.
저는 총 3가지 방법으로 풀이를 했습니다.
그 방법을 공유하겠습니다.

is_used 배열을 이용한 backtracking

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
#define endl '\n'
#define ASSERT(exp, msg) assert(exp &&msg)
using namespace std;
const int MAX = 8;
int N, M;
vector<int> seq;
bool is_used[MAX + 1];

void read_user_input() { cin >> N >> M; }

// 상태 공간 트리를 비트 마스킹 기법을 이용해 DFS로 순회
void dfs_bitmask(int level, int set) {
    if (level == M) {
        for (auto num : seq)
            cout << num << " ";
        cout << endl;
        return;
    }
    for (int i = 1; i <= N; i++) {
        if (set & (1 << i))
            continue;
        seq.push_back(i);
        dfs_bitmask(level + 1, set | (1 << i));
        seq.pop_back();
    }
}

// 상태 공간 트리를 DFS로 순회
void dfs(int level) {
    if (level == M) {
        for (auto num : seq)
            cout << num << " ";
        cout << endl;
        return;
    }

    for (int i = 1; i <= N; i++) {
        // 이미 뽑힌 숫자라면은 건너뛴다
        if (is_used[i])
            continue;
        seq.push_back(i);
        is_used[i] = true;
        dfs(level + 1);
        is_used[i] = false;
        seq.pop_back();
    }
}

// return n^k
int get_pow(int n, int k) {
    int ret = 1;
    for (int i = 0; i < k; i++) {
        ret *= n;
    }
    return ret;
}

void bruteforce() {
    int all_cases = get_pow(N + 1, M);
    for (int brute_case = 0; brute_case < all_cases; brute_case++) {
        int tmp_case = brute_case;
        while (!seq.empty())
            seq.pop_back();
        fill(is_used, is_used + MAX + 1, false);
        for (int i = 0; i < M; i++) {
            int cur_digit = tmp_case % (N + 1);
            if (cur_digit == 0)
                break;
            if (is_used[cur_digit])
                break;
            seq.push_back(cur_digit);
            is_used[cur_digit] = true;
            tmp_case /= (N + 1);
        }
        if (seq.size() == M) {
            for (auto it = seq.rbegin(); it < seq.rend(); it++)
                cout << *it << " ";
            cout << endl;
        }
    }
}

void solve() {
    // nPm을 구현하는 문제

    // is_used 배열을 사용한 백트래킹
    for (int i = 1; i <= N; i++) {
        seq.push_back(i);
        is_used[i] = true;
        dfs(1);
        seq.pop_back();
        is_used[i] = false;
    }

    // for (int i = 1; i <= N; i++) {
    // seq.push_back(i);
    // dfs_bitmask(1, (1 << i));
    // seq.pop_back();
    //}

    // (N + 1) 진법을 이용하여 구하기
    // bruteforce();
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    read_user_input();
    solve();
    return 0;
}

bitmasking을 이용한 backtracking

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
#define endl '\n'
#define ASSERT(exp, msg) assert(exp &&msg)
using namespace std;
const int MAX = 8;
int N, M;
vector<int> seq;
bool is_used[MAX + 1];

void read_user_input() { cin >> N >> M; }

// 상태 공간 트리를 비트 마스킹 기법을 이용해 DFS로 순회
void dfs_bitmask(int level, int set) {
    if (level == M) {
        for (auto num : seq)
            cout << num << " ";
        cout << endl;
        return;
    }
    for (int i = 1; i <= N; i++) {
        if (set & (1 << i))
            continue;
        seq.push_back(i);
        dfs_bitmask(level + 1, set | (1 << i));
        seq.pop_back();
    }
}

// 상태 공간 트리를 DFS로 순회
void dfs(int level) {
    if (level == M) {
        for (auto num : seq)
            cout << num << " ";
        cout << endl;
        return;
    }

    for (int i = 1; i <= N; i++) {
        // 이미 뽑힌 숫자라면은 건너뛴다
        if (is_used[i])
            continue;
        seq.push_back(i);
        is_used[i] = true;
        dfs(level + 1);
        is_used[i] = false;
        seq.pop_back();
    }
}

// return n^k
int get_pow(int n, int k) {
    int ret = 1;
    for (int i = 0; i < k; i++) {
        ret *= n;
    }
    return ret;
}

void bruteforce() {
    int all_cases = get_pow(N + 1, M);
    for (int brute_case = 0; brute_case < all_cases; brute_case++) {
        int tmp_case = brute_case;
        while (!seq.empty())
            seq.pop_back();
        fill(is_used, is_used + MAX + 1, false);
        for (int i = 0; i < M; i++) {
            int cur_digit = tmp_case % (N + 1);
            if (cur_digit == 0)
                break;
            if (is_used[cur_digit])
                break;
            seq.push_back(cur_digit);
            is_used[cur_digit] = true;
            tmp_case /= (N + 1);
        }
        if (seq.size() == M) {
            for (auto it = seq.rbegin(); it < seq.rend(); it++)
                cout << *it << " ";
            cout << endl;
        }
    }
}

void solve() {
    // nPm을 구현하는 문제

    // is_used 배열을 사용한 백트래킹
    // for (int i = 1; i <= N; i++) {
    // seq.push_back(i);
    // is_used[i] = true;
    // dfs(1);
    // seq.pop_back();
    // is_used[i] = false;
    //}

    // bitmasking을 이용한 백트래킹
    for (int i = 1; i <= N; i++) {
        seq.push_back(i);
        dfs_bitmask(1, (1 << i));
        seq.pop_back();
    }

    // (N + 1) 진법을 이용하여 구하기
    // bruteforce();
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    read_user_input();
    solve();
    return 0;
}

N+1 진법을 이용한 bruteforce

#include <algorithm>
#include <cassert>
#include <iostream>
#include <vector>
#define endl '\n'
#define ASSERT(exp, msg) assert(exp &&msg)
using namespace std;
const int MAX = 8;
int N, M;
vector<int> seq;
bool is_used[MAX + 1];

void read_user_input() { cin >> N >> M; }

// 상태 공간 트리를 비트 마스킹 기법을 이용해 DFS로 순회
void dfs_bitmask(int level, int set) {
    if (level == M) {
        for (auto num : seq)
            cout << num << " ";
        cout << endl;
        return;
    }
    for (int i = 1; i <= N; i++) {
        if (set & (1 << i))
            continue;
        seq.push_back(i);
        dfs_bitmask(level + 1, set | (1 << i));
        seq.pop_back();
    }
}

// 상태 공간 트리를 DFS로 순회
void dfs(int level) {
    if (level == M) {
        for (auto num : seq)
            cout << num << " ";
        cout << endl;
        return;
    }

    for (int i = 1; i <= N; i++) {
        // 이미 뽑힌 숫자라면은 건너뛴다
        if (is_used[i])
            continue;
        seq.push_back(i);
        is_used[i] = true;
        dfs(level + 1);
        is_used[i] = false;
        seq.pop_back();
    }
}

// return n^k
int get_pow(int n, int k) {
    int ret = 1;
    for (int i = 0; i < k; i++) {
        ret *= n;
    }
    return ret;
}

void bruteforce() {
    int all_cases = get_pow(N + 1, M);
    // N^M (1600만 대략)
    for (int brute_case = 0; brute_case < all_cases; brute_case++) {
        int tmp_case = brute_case;
        bool is_breaked = false;
        // M
        while (!seq.empty())
            seq.pop_back();
        // N
        fill(is_used, is_used + MAX + 1, false);
        // M
        for (int i = 0; i < M; i++) {
            int cur_digit = tmp_case % (N + 1);
            if (cur_digit == 0) {
                is_breaked = true;
                break;
            }
            if (is_used[cur_digit]) {
                is_breaked = true;
                break;
            }
            seq.push_back(cur_digit);
            is_used[cur_digit] = true;
            tmp_case /= (N + 1);
        }
        if (is_breaked == false && seq.size() == M) {
            for (auto it = seq.rbegin(); it < seq.rend(); it++)
                cout << *it << " ";
            cout << endl;
        }
    }
}

void solve() {
    // nPm을 구현하는 문제

    // is_used 배열을 사용한 백트래킹
    // for (int i = 1; i <= N; i++) {
    // seq.push_back(i);
    // is_used[i] = true;
    // dfs(1);
    // seq.pop_back();
    // is_used[i] = false;
    //}

    // bitmasking을 이용한 백트래킹
    // for (int i = 1; i <= N; i++) {
    // seq.push_back(i);
    // dfs_bitmask(1, (1 << i));
    // seq.pop_back();
    //}

    // (N + 1) 진법을 이용하여 구하기
    bruteforce();
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    read_user_input();
    solve();
    return 0;
}

참고로, 시간 초과가 나서 AC가 안됩니다. (연산횟수가 대충 10억 언저리로 나오네요…) 그저 이런 접근 방법이 있다는 걸 공유하고 싶었습니다.