[알고리즘]백트래킹(Backtracking)

백트래킹

백트래킹이란 해를 찾는 도중에 막히면 더 이상 깊이 들어가지 않고, 이전 단계로 되돌아가서 해를 찾아나가는 기법을 말한다.

백트래킹은 DFS의 변형

백트래킹은 DFS의 일종으로, 가능한 모든 경우의 수를 탐색한다.
가지치기(pruning)를 통해 조건을 만족하지 않는 경우에는 더 이상 탐색하지 않고 이전 단계로 돌아간다.
해결책을 찾을 때까지 탐색을 계속하며, 해를 찾으면 중지한다.
메모리를 적게 사용한다.

사용 예시

• 조합(Combination)과 순열(Permutation) 문제
• 스도쿠(Sudoku)와 같은 게임 문제
• n-queen 문제
  등이 있다.

백트래킹 적용

1. 재귀적으로 후보군을 탐색
2. 각 단계에서 제약 조건을 확인
3. 후보해가 해결책인지 확인
4. 만약 해결책이 아니라면 이전 단계로 되돌아가고 다른 후보 찾기

백크래킹 문제 N과 M

백준 문제 N과 M을 통해 백트래킹을 사용해보자.
https://www.acmicpc.net/problem/15649

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하는 문제이다.

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

const fs = require("fs");
const [N, M] = fs.readFileSync("./input.txt").toString().split(" ").map(Number);

let result = "";
function findCombination(arr) {
  // 후보해가 해결책인지 확인
  if (arr.length === M) {
    result += arr.join(" ") + "\n"; // 현재 조합을 결과에 추가
    return; // 가지치기: M개가 넘는 조합은 필요없다!
  }
  
  // 재귀적으로 후보군을 탐색
  for (let i = 1; i <= N; i++) {
    if (!arr.includes(i)) {
      arr.push(i);
      findCombination(arr);
      arr.pop(); // 백트래킹: 이전 단계로 되돌아가고 다른 후보 찾기
    }
  }
}
findCombination([], 1);

console.log(result);