[Algorithm] 백트래킹 알고리즘

백트래킹이란?

• 일반적으로 그래프/트리의 모든 원소를 완전 탐색하기 위한 목적으로 사용할 수 있다.
• DFS와의 차이점
  1) DFS는 일반적으로 완전 탐색 목적으로, 재귀 함수를 이용해 구현한다.
  2) 백트래킹도 재귀 함수를 이용해 구현하는 것이 일반적이지만, 단순히 완전 탐색하는 것이 아니라 조건에 따라서 유망한 노드로 이동한다.

그래프 표현 방식

1. 인접 행렬 (Adjacency Matrix)

	1	2	3	4
1	0	1	0	0
2	1	0	1	1
3	0	1	0	1
4	0	1	1	0

2. 인접 리스트 (Adjacency List)

• 1: 2
• 2: 1, 3, 4
• 3: 2, 4
• 4: 2, 3

백트래킹의 기본 형태

function recursive() {
  if (종료 조건을 만족한다면) {
    // 처리
  }
  for (자식 노드를 하나씩 확인하며) {
    if (임의의 조건을 만족한다면) {
      // 자식 노드 방문 처리
      recursive(); // 재귀 함수 호출
      // 자식 노드 방문 처리 해제
    }
  }
}

    1
   / \
  2   4
 / \
5   3
    \
     6

N-Queen 문제 해결 아이디어

• 매 재귀함수마다 실제로 N X N 모든 위치를 모두 볼 필요가 없다.
• [핵심] 맨 처음 행(row) 부터 차례대로 퀸을 놓는다고 생각하면 가지수를 훨씬 줄일 수 있다.
• N-Queen 문제는 가능한 조합을 계산하는 것이므로, 현재 행의 이전 행으로 돌아갈 필요가 없다.

• 백트래킹은 기본적으로 가능한 노드에 대하여 계속해서 재귀적으로 함수를 호출한다.
• 백트래킹은 모든 경우의 수를 탐색하기에 적합하다.
  • N-Queen 문제를 해결하기 위해서는 특정 위치(노드)의 가능 여부를 판단할 필요가 있다.
  • 가능한 노드 여부는 다음의 두 가지를 보면 된다.
  1) 같은 행에 있는지 체크: x1 == x2 / 같은 열에 있는지 체크: y1 == y2
  2) 대각선에 있는지 체크: abs(x1 - X2) == abs(y1 - y2)

N-Queen 예시코드

let n = 8; // 전체 맵의 크기
let queens = []; // 현재 체스판에 놓인 퀸의 위치 정보들
 
function possible(x,y) { // (x,y) 위치에 퀸을 놓을 수 있는지 확인 
  for (let [a,b] of queens) { // 현재꺼지 놓았던 모든 퀸의 위치를 하나씩 확인하며 
	if (a=x || b==y) return false; // 행이나 열이 같다면 놓을 수 없음 
    if (Math.abs(a-x) == Math.abs(b-y)) return false; // 대각선에 위치한 경우 놓을 수 없음 
  }
  return true;
}

let cnt = 0;
function dfs(row) {
	if(row == n) cnt +=1; // 퀸을 n개 배치할 수 있는 경우 카운트 
  	for(let i = 0 ; i<n ; i++) { // 현재 행에 존재하는 열을 하나씩 확인하며 
      if(!possible(row, i)) continue; //현재 위치에 놓을 수 없다면 무시 
      queens.push([row, i]);// 현재 위치에 퀸을 놓기 
      dfs(row+1); // 재귀함수 호출  
      queens.pop(); // 현재 위치에서 퀸을 제거하기 
    }
}

dfs(0);
console.log(cnt);



// 순열 코드 
const fs = require("fs");

const filePath = process.platform === "linux" ? "/dev/stdin" : __dirname + "/input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const n = +input.shift();
let arr = [];
for (let i = 1; i <= n; i++) arr.push(i);

let selected = [];
let visited = new Array(n).fill(false);
let answer = "";
function 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);


====================
[dfs] arr :  [ 1, 2, 3 ]  depth : 0
i :  0
selected :  [ 0 ]
visited :  [ true, false, false ]

====================
[dfs] arr :  [ 1, 2, 3 ]  depth : 1
i :  0
i :  1
selected :  [ 0, 1 ]
visited :  [ true, true, false ]

====================
[dfs] arr :  [ 1, 2, 3 ]  depth : 2
i :  0
i :  1
i :  2
selected :  [ 0, 1, 2 ]
visited :  [ true, true, true ]

====================
[dfs] arr :  [ 1, 2, 3 ]  depth : 3
result = 1,2,3
answer = 1 2 3 

i :  2
selected :  [ 0, 2 ]
visited :  [ true, false, true ]

====================
[dfs] arr :  [ 1, 2, 3 ]  depth : 2
i :  0
i :  1
selected :  [ 0, 2, 1 ]
visited :  [ true, true, true ]

====================
[dfs] arr :  [ 1, 2, 3 ]  depth : 3
result = 1,3,2
answer = 1 2 3 
1 3 2 

i :  2
i :  1
selected :  [ 1 ]
visited :  [ false, true, false ]

====================
[dfs] arr :  [ 1, 2, 3 ]  depth : 1
i :  0
selected :  [ 1, 0 ]
visited :  [ true, true, false ]

====================
[dfs] arr :  [ 1, 2, 3 ]  depth : 2
i :  0
i :  1
i :  2
selected :  [ 1, 0, 2 ]
visited :  [ true, true, true ]

====================
[dfs] arr :  [ 1, 2, 3 ]  depth : 3
result = 2,1,3
answer = 1 2 3 
1 3 2 
2 1 3 

i :  1
i :  2
selected :  [ 1, 2 ]
visited :  [ false, true, true ]

====================
[dfs] arr :  [ 1, 2, 3 ]  depth : 2
i :  0
selected :  [ 1, 2, 0 ]
visited :  [ true, true, true ]

====================
[dfs] arr :  [ 1, 2, 3 ]  depth : 3
result = 2,3,1
answer = 1 2 3 
1 3 2 
2 1 3 
2 3 1 

i :  1
i :  2
i :  2
selected :  [ 2 ]
visited :  [ false, false, true ]

====================
[dfs] arr :  [ 1, 2, 3 ]  depth : 1
i :  0
selected :  [ 2, 0 ]
visited :  [ true, false, true ]

====================
[dfs] arr :  [ 1, 2, 3 ]  depth : 2
i :  0
i :  1
selected :  [ 2, 0, 1 ]
visited :  [ true, true, true ]

====================
[dfs] arr :  [ 1, 2, 3 ]  depth : 3
result = 3,1,2
answer = 1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 

i :  2
i :  1
selected :  [ 2, 1 ]
visited :  [ false, true, true ]

====================
[dfs] arr :  [ 1, 2, 3 ]  depth : 2
i :  0
selected :  [ 2, 1, 0 ]
visited :  [ true, true, true ]

====================
[dfs] arr :  [ 1, 2, 3 ]  depth : 3
result = 3,2,1
answer = 1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1 

i :  1
i :  2
i :  2
1 2 3 
1 3 2 
2 1 3 
2 3 1 
3 1 2 
3 2 1