[백준 15649] N과 M (1)

🔗문제 풀러가기
단계별로 풀어보기 단계 22의 1번째 문제이다.

문제 분석

백트래킹 알고리즘을 이용하여 문제를 해결하였다.

백트레킹?
백트래킹(backtracking)이란? : 해를 찾는 도중 해가 아니어서 막히면, 되돌아가서 다시 해를 찾아가는 기법.
최적화 문제와 결정 문제를 푸는 방법이 된다.

코드

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

int n, m;
vector<int> vec;

void Backtrack(int n, int m)
{
    if (vec.size() == m)
    {
        for (auto i : vec)
        {
            cout << i << " ";
        }
        cout << "\n";
        return;
    }

    for (int i = 1; i <= n; i++)
    {
        if (find(vec.begin(), vec.end(), i) == vec.end())
        {
            vec.push_back(i);
            Backtrack(n,m);
            vec.pop_back();
        }
    }
}

int main()
{
    cin >> n >> m;
    Backtrack(n, m);
}

해석

1. n과 m을 입력받아 Backtrack을 실행한다.
2. 만약 벡터의 사이즈가 m이 된다면 벡터의 요소들을 모두 출력하고 재귀를 종료한다.
3. 그렇지 않다면 n까지 반복문을 돌리며 지금 벡터에 i가 없다면 벡터에 저장한 후 Backtrack을 다시 실행한다.
4. 실행이 끝나면 벡터에서 지워준다.