[BOJ 15649] 백트래킹, N과 M (1)

백트래킹
- DFS와 유사하게 진행되나, 해당 노드의 유망성을 보고 진행을 결정한다.

[BOJ 15649] N과 M (1) 문제

1부터 N까지의 수로 수열을 만드는 문제이다.
이때 수열은 M개의 수로 이루어져 있으며 순서는 상관이 없다.

C++ 풀이

1. 백트래킹 코드를 짤 때는, 방문 여부를 표시해둘 visited 배열을 만드는 것이 중요하다
2. 만약 이미 visited한 인덱스라면 건너뛰거나 / 다시 되돌아가는 일이 필요하다.
3. 다시 되돌아왔다면 visited 배열을 다시 0으로 표시해주어야 다음 수열에서도 해당 인덱스를 사용할 수 있다.

아래 코드에서 방문여부는 visited 배열에, 수열의 정보는 arr 배열에 저장하였다.

cnt 변수는 arr 배열의 인덱스로 사용하였고, cnt가 M이 될 경우 arr에 저장된 수열을 출력해주는 코드이다.

#include <iostream>

using namespace std;

int visited[9]={0,};
int arr[9]={0,};
int N, m;
void dfs(int cnt);

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

void dfs(int cnt){
	//PRINT
    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]==0)
        {
            visited[i]=1;
            arr[cnt]=i;
            dfs(cnt+1);
            visited[i]=0;
        }
    }
}