728x90
- 백트래킹 : 가능한 모든 후보군을 탐색하는 알고리즘
- 백트래킹의 구현 : 배열의 활용
#include <iostream>
using namespace std;
int n, m;
int arr[8];
bool used[8];
void func(int k){
if(k == m){
for(int i = 0 ; i < m ; i++){
cout << 1 + arr[i] << ' ';
}
cout << "\n";
return;
}
for(int i = 0 ; i < n ; i++){
if(!used[i]){
arr[k] = i;
used[i] = 1;
func(k+1);
used[i] = 0;
}
}
}
int main(void){
cin >> n >> m;
func(0);
}ex. 백준 15649 - N과 M
15649번: N과 M (1)
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다. 수열은 사전 순으로 증가하는 순서로 출력해
www.acmicpc.net
1. n, m은 입력 데이터
2. arr은 완성된 수열
3. used는 해당 숫자의 방문 여부를 확인
- i번째 숫자에 방문하지 않은 경우 해당 숫자를 수열 맨 뒤에 추가
- used에 방문 표시 후, k+1번째로 func 함수 호출
- 함수 동작 후 used는 방문하지 않은것으로 수정
4. func 함수는 입력받은 수열 길이(m)를 만족할 경우(k), 수열을 출력
728x90