백트래킹이 이해가 잘 안되었다.

알고리즘 강의를 통해서 백트래킹에 대한 대략적인 이해가 되었으나 코드로서 이해는 정말 어려웠다. 일단 글로서 적어가면서 이해를 돕기로한다. 

 

백트래킹의 기본 문제로서 백준 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) 재귀함수가 시작됨 여기서 뭔가 또 잘못되었는데

 

대략적인 코드의 흐름을 알겠으나 이해가 좀 더 필요함.