[알고리즘] 백 트래킹 , 백준 12101

오늘은 백트래킹에 대해 알아보겠습니다.

⭐️ 백트래킹(BackTracking)이란 ?

백트래킹은 완전 탐색 문제에서 사용되는 트리 탐색 알고리즘입니다. 완전 탐색이란 문제를 해결하기 위해 모든 가능한 경우의 수를 탐색하면서 해답을 찾는 탐색 알고리즘입니다. 주로 DFS 혹은 BFS를 이용해서 구현하는데 , 문제의 조건에 따라 (모든 경우의 수 인지 , 최단 거리인지) DFS 혹은 BFS를 선택하면 될 것 같습니다.

백트래킹의 동작 프로세스는 다음과 같습니다.
1. 선택 : 현재 상태에서 다음 단계로 진행할 수 있는 선택지를 고릅니다.
2. 조건 확인 : 선택지가 문제의 조건에 부합하는지를 확인합니다.
3. 해결 : 조건을 만족한다면 다음 depth로 넘어갑니다. 이 과정에서 재귀적으로 다음 선택을 진행합니다.
4. 되돌아가기 : 조건을 만족하지 않거나 모든 가능한 선택지를 시도한 경우 , 이전 단계로 되돌아가서 다른 선택을 시도합니다.

⭐️ 백준 12101 : 1,2,3더하기 2

문제 조건은 1,2,3만으로 주어진 n값을 나타내는 모든 경우의 수를 구한 후 , k번 째에 오는 식을 구해야하기 때문에 dfs를 이용하여 문제를 풀었습니다.

function solution(input) {
    const [n, k] = input;

    const result = [];
    const bt = (sum, el) => {
        // sum이 n이라면 이후 과정을 진행하지 않고 , 결과에 넣어줌
        if (sum === n) return result.push([...el]);
		
        // 1,2,3을 선택
        for (let i = 1; i <= 3; i++) {
            // 조건 확인
            if (sum + i <= n) {
            	// 조건을 만족하므로 다음 depth로 넘어감
                sum += i;
                el.push(i);
                bt(sum, el);
                
                // i의 값에 따라 만족하는 경우의 수들을 모두 거친 후 , i+1값으로 넘어갈 준비
                el.pop();
                sum -= i;
            }
        }
    };
    bt(0, []);
    result[k - 1] ? console.log(result[k - 1].join("+")) : console.log(-1);
}

const rl = require("readline").createInterface({
    input: process.stdin,
    output: process.stdout,
});

rl.on("line", (line) => {
    solution(line.split(" ").map(Number));
    process.exit();
});