알고리즘/백준 알고리즘
백준 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문이 돌아가면, 모든 경우의 수를 다 탐색하게 됩니다.