[백준] 15649번 - 백트래킹 알고리즘, DFS

#include <iostream>
#define MAX 9
using namespace std;

int n, m;
int arr[MAX] = { 0, };
bool visited[MAX] = { 0, };

void dfs(int cnt)
{
    if (cnt == m)
    {      
        for (int i = 0; i < m; i++)
            cout << arr[i] << ' ';
        cout << '\n';
        return;
    }
    for (int i = 1; i <= n; i++)
    {
        if (!visited[i])
        {
            visited[i] = true;
            arr[cnt] = i;
            dfs(cnt + 1);
            visited[i] = false;
        }
    }
}

int main() {
    cin >> n >> m;
    dfs(0);
}

 

1부터 N까지 자연수 중에 중복없이 M개를 뽑는 수열을 모두 출력한다.

이 과정에서 백트래킹을 이용한 DFS(깊이 기반 탐색)를 이용한다. 

 

i루프가 1부터 돌면서 방문하지 않은 노드에 방문했다고 true로 체크하고 

cnt에 1을 더해서 재귀 호출하고 동일하게 반복한다. 그리고 조건을 달성했을 때 

(cnt가 m과 같아졌을 때) return으로 함수를 종료하고 

재귀호출로 스택에 쌓여있던 함수들을 통해 역으로 다시 돌아와서 탐색을 시작한다.

예시로 스택에 dfs(0), dfs(1), dfs(2) 순서로 쌓이기 때문에 dfs(2)함수가 종료될 경우

dfs(1)이 실행된 시점으로 돌아와서 탐색을 진행한다.