💡 백트래킹(backtracking)이란?
: 현재 상태에서 가능한 모든 후보군을 따라 들어가면서 탐색하는 알고리즘
브루트 포스 중에서도, 재귀를 이용해 탐색하는 것을 백트래킹이라고 한다.
해를 만들어 나가면서 답이 될 가능성이 없는 해를 미리미리 쳐내는 방식(가지치기)
백트래킹 = 재귀+dfs(+상태공간트리)
전략
- 예제들을 꼼꼼히, 많이 풀자.
- 기본적인 코드의 형태를 익혀두자.
문제를 통해 겪어보기
💡 문제
자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.
- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
입력
첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)
출력
한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.
수열은 사전 순으로 증가하는 순서로 출력해야 한다.
🤔 내가 생각한 아이디어
관찰을 통해 이해해보기
인풋으로
4 2가 들어왔다고 가정하자. 그럼 1부터 4까지의 자연수에서 중복 없이 2개를 고른 수열이 된다. 대충 조합을 재귀로 구현해라, 정도의 문제인 것 같다. 그리고 사전 순으로 증가하는 순서로 출력해야 한다.
여기서 중요한 조건은 중복 없이라는 조건일 것 같다. 이 조건에 의하여, 중복 체크를 해주어야하고, 해당 후보군을 방문했는지 안했는지 판단할 수 있는 vis[n] 을 선언해야 할 것 같다.
대충 문제의 틀을 상태공간 트리로 나타내면, 이렇게 그림을 그리면 될 것 같다.
해당 그림을 살펴보자. 사전순으로 증가하는 순서대로 출력해야 하므로, 후보군은 1부터 n까지의 자연수다. for문으로 1부터 n까지를 돌며, ans vector에 push해주는데, 중복 체킹을 위해서 vis[n]배열을 선언해주고, 기존에 방문했던 자연수 n이면 제끼고(continue), 그 다음으로 큰 자연수를 방문해준다.
depth==m이면 ans vector에 저장된 값들을 그대로 출력해주면 되고, 아니면 depth++;를 해주면서 계속 재귀호출해주면 된다.
한 가지 또 주의할 점이 재귀함수를 설계할 때, 재귀함수 설계 원칙에 따라
1. 종료조건 2. 핵심로직 부분을 아주 잘 구분해 설계해야함에 유의하자.
⚒️ 뚝딱뚝딱 설계
//전역에 n과 m, 방문체킹해줄 vis[n],
//정답 저장할 ans 벡터 선언
void solve(int depth) {
// ** 1. 재귀의 기본형태: 종료조건 포함 **
// depth가 m이면, ans배열에 저장된 값들 출력 후 종료
// ** 2. 핵심로직이 들어가는 부분 **
// 후보군 노드는 1부터 n까지의 자연수 for(int candid = 1 to n)
// 중복이 없어야 하니까, 각 후보군에 대하여 방문처리해주는 vis[candid]필요
// vis[candid] =true라면, 다른 후보군 노드 탐색
// vis[cnadid]=false라면, 방문 처리 후
// depth 하나 증가시켜주면서 solve(depth+1) 재귀호출
// ★중요★ 재귀호출 끝나면, vis처리했던 candid들 다시 방문미처리로 초기화해주어야 함.
}💻 정답 코드
// 15649 n과 m(1)
// 백트래킹 입문 문제
#include <iostream>
using namespace std;
int n, m; //nCm
bool vis[10] = {false, }; //중복 체킹함수, false이면 아직 방문미처리
int ans[10]; // 정답 수열 담을 배열 ans선언
void solve(int depth){
if(depth == m) { //1. 종료조건
for(int i = 0; i < m; i++) {
cout << ans[i] << " ";
}
cout << "\n";
}
//2. 핵심로직
for(int candid = 1; candid <= n; candid++) {
if(vis[candid]) continue; //이미 방문했으면 다음 후보군
vis[candid]=true; ans[depth]=candid;//아니면 방문체킹해주고, ans배열에 해당 후보군 저장
solve(depth+1);
vis[candid]=false; //재귀호출이 끝나면, 다시 방문 안된 상태로 초기화.
}
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(0);
cin >> n >> m;
solve(0);
}