알고리즘/백준 알고리즘

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

빠켱이 2020. 8. 13. 01:36

15649번은 백준에 있는 가장 기본적인 백 트레킹 문제입니다.

백 트레킹이란 가능한 모든 경우의 수를 탐색하는 방법이라고 이해할 수 있습니다.

좀 더 쉽게 이해하자면 순열과 조합 중 순열에 해당하는 방법입니다.

#include <iostream>
using namespace std;

int n, m;
int arr[9] = { 0 };		//N값에 대한 숫자배열
bool visited[9] = { false };	//방문여부 check함수
void dfs(int cnt);

int main() {
	scanf("%d %d", &n, &m);
	dfs(0);
}

void dfs(int cnt)
{
	if (cnt == m)
	{
		for (int i = 0; i < m; i++)
			printf("%d ", arr[i]);
		printf("\n");
		return;
	}
	for (int i = 1; i <= n; i++)
	{
		if (visited[i] == false)
		{
			visited[i] = true;
			arr[cnt] = i;
			dfs(cnt + 1);
			visited[i] = false;
		}
	}
}

dfs와 같은 원리라서 함수명을 dfs를 사용하였고, 해당 문제를 처음 접근하면 이해가 잘 안 될 수도 있지만 프로그램을 살펴보면,

1. dfs에 0이라는 숫자를 인자로 넘겨주면서 시작합니다.

2. 함수를 살펴보면 cnt, m이라는 변수가 있는데 cnt는 인자로 받은 정수이고 m은 초기에 입력받은 숫자의 개수입니다.

3. cnt == m이 아닐 때는 for문을 돌면서 false인지 확인하고 맞으면 cnt+1을 인자로 넘기면서 재귀

4. 이후 cnt == m의 조건이 성립하였을 때 내부를 실행시키고 return을 하게 되면 재귀가 모두 종료됩니다.

5. 재귀가 모두 종료되며 나올 때 true로 바꿨던 visited함수를 다시 false로 바꾸고 이후 순차적으로 for문이 돌아가면, 모든 경우의 수를 다 탐색하게 됩니다.