✏️ 백트래킹이란?
일반적으로 그래프/트리의 모든 원소를 완전 탐색하기 위한 목적으로 사용할 수 있습니다.
DFS는 일반적으로 완전 탐색 목적으로 재귀 함수를 사용해 구현합니다. 백트래킹도 재귀 함수를 이용해 구현하는 것이 일반적이지만 단순히 완전 탐색 하는 것이 아니라 조건에 따라서 유망한 노드로 이동합니다.
즉 값을 찾아가는 도중, 지금의 경로가 값이 될 것 같지 않으면 그 경로를 더이상 가지 않고 되돌아가는 방법을 말합니다.
✏️ 코드 예시
- n과 m 문제
자연수 n과 m이 주어졌을 때 조건을 만족하는 길이가 m인 수열을 모두 구하는 문제
조건 - 1부터 n까지 자연수 중에서 중복없이 m개를 고른 수열
ex) 4, 2 가 주어지면 1~4까지의 숫자에서 길이가 2인 수열을 구함 [1, 2], [1, 3], [1, 4], [2, 1], [2, 3], [2, 4] ...
💡문제 해결 아이디어
- 모든 순열의 수를 고려하기 위해 재귀 함수(백트래킹)을 사용할 수 있습니다.
- 하나의 순열을 트리에서 리프 노드까지의 경로로 생각할 수 있습니다. 이 때 m개의 원소를 뽑는 순열을 고려하는 것이므로 깊이는 m과 같습니다.
- 원소를 중복해서 선택하지 않기 때문에 방문처리 배열을 사용할 수 있습니다. 즉 한번 선택된 원소는 다음 재귀 함수에서 다시 선택되지 않습니다.
function solution(n, m) {
// 순열을 계산하고자 하는 원소가 담긴 배열 [1, 2, 3, 4]
let arr = Array.from({ length: n }, (v, i) => i + 1);
// 각 원소의 인덱스 별 방문 여부
let visited = new Array(n).fill(false);
// 현재 순열에 포함된 원소
let selected = [];
let answer = "";
function dfs(arr, depth) {
// 모든 순열을 확인하는 부분
if (depth === m) {
let result = []; // 순열 결과 저장
for (let i of selected) result.push(arr[i]);
for (let x of result) answer += x + " ";
answer += "\n"; // 줄바꿈 처리
return;
}
for (let i = 0; i < arr.length; i++) {
if (visited[i]) continue; // 이미 처리된 원소라면 무시하고 넘어감
selected.push(i); // 현재 원소 선택
visited[i] = true; // 방문처리
dfs(arr, depth + 1); // 재귀함수 호출
selected.pop(); // 현재 원소 선택 취소
visited[i] = false; // 원소 방문 처리 취소
}
}
dfs(arr, 0);
return answer;
}
console.log(solution(4, 2));