[C++/BackTracking/백준] 15649번 N과 M (1)

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

---

DFS를 이용한 백트래킹 문제입니다. 조건과 부합하면 화면에 출력하고 return하여 백트래킹 해줍니다. 

visited 배열로 중복사용되지 않게 처리해주고 return이 되면 다시 마지막에있는 숫자를 pop_back()과 vistied[i] = false로 미 방문 처리하여 다음 순열에서 사용가능하게 처리합니다.

 

전체소스코드

#include <iostream>
#include <algorithm>
#include <string>
#include <vector>

using namespace std;


int n,m;
bool visited[8];
int arr[8];
vector<int>v;
void Print()
{
    for(int i=0;i<v.size();i++)
    {
        cout<<v[i]<<" ";
    }
    cout<<endl;
    return;
}
void dfs(int cnt)
{
    if(cnt==m)
    {
        Print();
        return;
    }

    for(int i=0;i<n;i++)
    {
        if(visited[i])
            continue;
        visited[i] = true;
        v.push_back(arr[i]);
        dfs(cnt+1);
        v.pop_back();
        visited[i] = false;
    }

}
int main()
{
    cin>>n>>m;
    for(int i=0;i<n;i++)
    {
        arr[i] = i+1;
        visited[i] = false;
    }
    dfs(0);

}