백트래킹이 이해가 잘 안되었다.
알고리즘 강의를 통해서 백트래킹에 대한 대략적인 이해가 되었으나 코드로서 이해는 정말 어려웠다. 일단 글로서 적어가면서 이해를 돕기로한다.
백트래킹의 기본 문제로서 백준 10974 모든 순열이라는 문제가 있다.
const input = require("fs").readFileSync("example.txt").toString().trim();
const n = Number(input);
let arr = [];
for (let i = 1; i <= n; i++) {
arr.push(i);
}
let visited = new Array(n).fill(false);
let selected = [];
let answer = "";
const dfs = (arr, depth) => {
if (depth == n) {
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);
console.log(answer);
정답은 이러한데 기본적으로 깊이를 설정하여 마지막 깊이까지 들어갔을 때 종료하는 부분과 탐색을 해가는 반복문 부분으로 나뉜다. 내가 제일 이해가 어려웠던 부분은 재귀함수 부분이다. 잠깐이라도 헷갈렸던 부분을 정리해보자면
1) 재귀함수가 끝나기 까지 selected.pop();과 visited[i] = false;이 두 라인은 실행되지 않는다. 내가 잘못 생각한 부분은 뭔가 투 트랙으로 진행되나 싶었는데 코드를 차례대로 실행되는게 원칙이다.
2) return은 해당 함수만 종료 시킨다. 지금같은 재귀 함수일 때 전체 함수를 종료시키는 것은 아니다.
3) break와 continue의 차이
두 가지를 먼저 해소하고 나도 나보고 이걸 구현하라고하면 솔직히 엄두가 안났다. 뭔가 코드의 그림이 안그려지니 답답했다. 일단 오늘은 일일히 쳐서 코드의 진행을 살펴보기로 하였다.
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)가 실행된다.
depth가 3일때 함수가 종료된다.
selected.push(0)로 selected는 [0]이 됨
vistied[0]은 false니까 아래로 넘어감
vistied[0] = true로 visited는 [true, false, false]이 됨
dfs(arr, 0 + 1) 재귀함수가 시작됨
depth가 3이 아니므로 반환 조건을 뛰어넘고 다시 for loop로 들어감
visited[0] 이미 true니까 i = 1로 넘어감
vistied[1]은 false니까 아래로 넘어감
selected.push(1)로 selected는 [0, 1]이 됨
vistied[1] = true로 visited는 [true, true, false]이 됨
dfs(arr, 1 + 1) 재귀함수가 시작됨
depth가 3이 아니므로 반환 조건을 뛰어넘고 다시 for loop로 들어감
visited[0] 이미 true니까 i = 1로 넘어감
visited[1] 이미 true니까 i = 2로 넘어감
vistied[2]은 false니까 아래로 넘어감
selected.push(2)로 selected는 [0, 1, 2]이 됨
vistied[2] = true로 visited는 [true, true, true]이 됨
dfs(arr, 2 + 1) 재귀함수가 시작됨
depth가 3이므로 첫 번째 반환 조건문에 해당됨
answer에 1 2 3 \n이 되고 맨 마지막 dfs(arr, 3) 함수가 종료됨
dfs(arr, 1 + 1) 재귀함수가 이어짐
i = 2 일 때 반복문에서 재귀함수 이후 코드를 실행
selected.pop()로 selected는 [0, 1]이 됨
vistied[2] = false로 visited는 [true, true, false]이 됨
for문이 종료되고 dfs(arr, 2)가 종료됨
dfs(arr, 0 + 1) 재귀함수가 이어짐
i = 1 일 때 반복문에서 재귀함수 이후 코드를 실행
selected.pop()로 selected는 [0]이 됨
vistied[1] = false로 visited는 [true, false, false]이 됨
i = 2 일 때 반복문 실행
vistied[2]은 false니까 아래로 넘어감
selected.push(2)로 selected는 [0, 2]이 됨
vistied[2] = true로 visited는 [true, false, true]이 됨
dfs(arr, 1 + 1) 재귀함수가 시작됨 (여기서 헷갈림)
depth가 3이 아니므로 반환 조건을 뛰어넘고 다시 for loop로 들어감
visited[0] 이미 true니까 i = 1로 넘어감
selected.push(1)로 selected는 [0, 2, 1]이 됨
vistied[1] = true로 visited는 [true, true, true]이 됨
dfs(arr, 2 + 1) 재귀함수가 시작됨
depth가 3이므로 첫 번째 반환 조건문에 해당됨
answer에 1 3 2 \n이 되고 맨 마지막 dfs(arr, 3) 함수가 종료됨
dfs(arr, 1 + 1) 재귀함수가 이어짐
i = 1 일 때 반복문에서 재귀함수 이후 코드를 실행
selected.pop()로 selected는 [0, 2]이 됨
vistied[1] = false로 visited는 [true, false, true]이 됨
i = 2 일 때 반복문 실행
vistied[2]은 true로 dfs(arr, 1 + 1) 종료
맨 처음 dfs(arr, 0)로 돌아옴
i = 0 일 때 반복문에서 재귀함수 이후 코드를 실행
selected.pop()로 selected는 [0]이 됨
vistied[0] = false로 visited는 [false, false, true]이 됨
i = 1 일 때 반복문 실행
selected.push(1)로 selected는 [0, 1]이 됨
vistied[1] = false로 visited는 [false, true, true]이 됨
dfs(arr, 1 + 1) 재귀함수가 시작됨
depth가 3이 아니므로 반환 조건을 뛰어넘고 다시 for loop로 들어감
vistied[0]은 false니까 아래로 넘어감
selected.push(0)로 selected는 [0, 1, 0]이 됨
vistied[0] = true로 visited는 [true, true, true]이 됨
dfs(arr, 2 + 1) 재귀함수가 시작됨 여기서 뭔가 또 잘못되었는데
대략적인 코드의 흐름을 알겠으나 이해가 좀 더 필요함.