백준 : 15649 N과 M(1)(C++14)_DFS, 백트레킹

핵심

DFS : 재귀로 구현가능하다.
백트레킹 : 이전 단계로 한단계 후퇴하면서 경우의 수를 확인하는 것 중요점은 가지치기(필요없는 경우는 거르는 것)을 통해야한다.

*알게된 점 : cout << endl 과 cout << '\n' 의 속도 차이가 많이 난다 endl 은 버퍼를 비워주는 작업이 필요하기 때문에
줄 바꿈에 대해서는 '\n' 을 이용하자!

풀이

// 2020-05-26 wsshin

#include <iostream>
#include <stdio.h>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

vector<int> m_vecResult;
vector<int> m_vecVisited;

int m_OutSize;
int m_NumSize;

int DFS(int CurSize);

int main()
{
    int m;
    int n;

    cin >> n >> m;

    m_OutSize = m;
    m_NumSize = n;

    int CurSize = 0;

    for (int i = 0; i < m_NumSize; i++)
    {
        m_vecVisited.push_back(0);
    }

    CurSize = DFS(0);

    return 0;
}

int DFS(int CurSize)
{
    if (CurSize == m_OutSize)
    {
        for (int i = 0; i < m_vecResult.size(); i++)
        {
            cout << m_vecResult[i] << ' ';
        }
        cout << '\n';
        return 0;
    }

    for (int i = 0; i < m_NumSize; i++)
    {
        if (m_vecVisited[i] == 1) continue;

        m_vecResult.push_back(i + 1);
        m_vecVisited[i] = 1;
        DFS(CurSize + 1);
        m_vecResult.pop_back();
        m_vecVisited[i] = 0;
    }

    return 0;
}