[백준 15649] N과 M (1)

● 문제 : 백준 15649번 : N과 M (1)

15649번: N과 M (1)

 

● 알고리즘

- 재귀함수

- 백트래킹

[백트래킹]

 

● 문제 풀이

백트래킹을 통해 조건에 맞는 경로만 탐색한다. 조건은 간단하다. 방문했는지를 검사하는 visit 배열을 하나 만들고, 이미 방문을 했다면 경로에서 제외시키고 방문하지 않은 경로만 탐색한다. 백트래킹은 기본적으로 DFS로 구현할 수 있는데, DFS는 일반적으로 재귀함수로 이루어져 있다. cnt라는 매개변수를 1씩 늘려가며 문제에서 입력받은 M과 같을 때까지 재귀함수가 종료되도록 한다. 

예를 들어, N=3, M=2라고 하면 

1) DFS(0)

2) visit[1]=1, arr.push_back(1) -> arr={1}

3) DFS(1)

4) 1은 이미 방문했으므로 제외시키고 2 방문

visit[2]=1, arr.push_back(2) -> arr={1,2}

5) DFS(2)

cnt==M(2)이므로 1,2 출력 후 재귀함수 종료 -> 4)로 돌아감

6) visit[2]=0, arr.pop_back() -> arr={1}

7) visit[3]=1, arr.push_back(3) -> arr={1,3}

8) DFS(2)

cnt==M(2)이므로 1,3 출력 후 재귀함수 종료 -> 7)로 돌아감

9) visit[3]=0, arr.pop_back() -> arr={1}

10) for문 끝났으므로 재귀함수 종료 -> 2)로 돌아감

11) visit[1]=0, arr.pop_back() -> arr={}

12) 위 방법을 반복하며 수열을 출력한다. 

 

● 코드

#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <algorithm>
#include <string>
#include <cstring>
#include <climits>
#include <random>
#include <cmath>
#include <set>
#include <ctime>
using namespace std;
using ll = long long;
using ii = pair<int, int>;

int N, M;
vector<int>arr;
vector<int>visit(9);
void DFS(int cnt)
{
	if (cnt == M)
	{
		for (int i = 0; i < arr.size(); i++)
			cout << arr[i] << " ";
		cout << "\n";
		return;
	}

	for (int i = 1; i <= N; i++)
	{
		if (visit[i] == 0)
		{
			visit[i] = 1;
			arr.push_back(i);
			DFS(cnt + 1);
			visit[i] = 0;
			arr.pop_back();
		}
	}
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> N >> M;
	DFS(0);
	return 0;
}