[백준 15649번, 15650번 / C++] N과 M

 

 

 

dfs, 백트래킹, 재귀 를 사용해 푸는 문제이다.

DFS - 깊이우선 탐색으로 수열을 제공받는 길이 M 까지 출력하기 위해서 사용하는 알고리즘

백트래킹 - 해를 찾는 도중, 해가 아니어서 막히면 다시 돌아가서 해를 찾는 방법

재귀 - 함수 내에서 자기 자신을 다시 호출하는 함수



처음에 dfs 함수를 0 을 넣어 호출해

1 2, 1 3, 1 4, 2 1 .... 등등 출력할 수 있도록



재귀함수 탈출조건을 명시해준 후 ( 함수 인풋이 M과 같으면 == 수열의 개수가 M개로 채워지면)

탈출 시에는 벡터에 담아두었던 원소를 전부 출력한다.



탈출조건 만족 못할 시에는 순회 하면서 벡터에 넣어주고 dfs(+1) 만큼 재귀호출 해준다.

 

 

 

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

bool visited[10] = { false };
vector<int> v;

int N, M;


void dfs(int cnt)
{
    if (cnt == M)
    {
        for (auto i : v)
            cout << i << " ";
        cout << '\n';
        
        return;
    }
    else
    {
        for (int i = 1; i <= N; i++)
        {
            if (!visited[i])
            {
                visited[i] = true;
                v.push_back(i);
                dfs(cnt + 1);
                visited[i] = false;
                v.pop_back();
            }
        }
    }

}


int main() {

    cin >> N >> M;
    dfs(0);

    return 0;
}

 

 

15650번

#include <iostream>
#include <vector>


using namespace std;

vector<int> v;

bool visited[10] = { false };

int N, M;

void dfs(int input)
{

    if (input == M)
    {
        for (auto i : v)
        {
            cout << i << " ";
            
        }
        cout << '\n';
        return;
    }
    else
    {
        for (int i = 1; i <= N; i++)
        {
            if (!visited[i])
            {
                if (!v.empty() && i < v.back()) continue;

                visited[i] = true;
                v.push_back(i);

                dfs(input + 1);

                visited[i] = false;
                v.pop_back();



            }
        }
    }
    
        


}

int main() {

    cin >> N >> M;

    

    dfs(0);
 


    return 0;
}