백트래킹

1. 개념

• 모든 경우의 수를 확인해야할때 백트래킹을 사용한다.
• for로는 확인이 불가한 경우(깊이가 달라질때)

🤨 깊이란 무엇일까?

for(...){
	for(...){}
}

• 여기서 for문이 두번 반복된다. 여기서 깊이는 2인 것이다.

🤨 그렇다면 깊이 달라진다는 것은 무엇일까?

• 돌아가는 for의 반복이 정해지지 않고 계속 달라진다는 것이다.

2. 👍 백트래킹 원리

• 재귀함수를 통해서 for을 계속 늘려서 깊이를 설정할 수 있다.

 const dfs=(num)=>{
 	1. for(1~N); //for문에서 1개를 선택해서 결과값에 추가한다.
   //for문에서 1개를 선택하고 다음에 또 같은 값을 선택하면 안되니깐 
   // 중복 없이 N개를 골라야 하기에 방문여부를 체크하여 
   //방문을 안한것만 선택하여 재귀함수를 돌려준다.
   2. 방문여부 체크; 
   3. 결과값에 추가;
   4. 방문여부 체크;
   5. dfs(num+1);
 }

3. 시간복잡도

N^N : 중복이 가능, N이 8일때까지 가능

1~N
1~N
.
.
.
1~N(N번쨰)
===>N*N*N*N...

N! : 중복 불가능, N이 10일때까지 가능

1~N
1~(N-1)
1~(N-2)
.
.
1~2
1(N번쨰)
==> N*(N-1)*(N-2)...*1

👍그래서 백트래킹은 N이 10언저리에서만 가능하다.

4. 백트래킹의 자료 구조

• 방문 여부를 확인하는 배열bool[]이 필요하다
• 선택한 값을 입력하는 배열int[] 이 필요하다.

😁 15649번 : N과 M (1)

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

입력/시간복잡도

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

--> N과 M이 10보다 작은 8이기에 백트래킹으로 풀 수 있다.

입출력 예시

🤨 아이디어

• 1부터 N중에 하나를 선택한 뒤
  -> for문으로 선택
• 다음 1부터 N부터 선택할때 이미 선택값이 아닌 경우 선택
  -> 방문여부 체크
• M개를 선택할 경우 출력

내 코드

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';

let input = fs.readFileSync(filePath).toString().trim().split('\r\n');
let [n,m] = input[0].split(' ').map(Number); //3(n) 2(m)

const solution=(n,m)=> {
    const seq = [];
    const visited = [...Array(n+1)].fill(false);//[ false, false, false ]
    let result = "";
    
  const dfs=(num)=>{
    if(num===m) {
        result+= `${seq.join(' ')}\n`;
        return
    }
    for(let i=1; i<=n; i++){
        // visited[i]가 false인것 아직 방문하지 않앗으면
        if(visited[i]===false){
            //방문하고 방문했으니 true로 바꿔준다.
            visited[i]=true;
            seq.push(i);
            dfs(num+1);
            // seq.pop을 넣어주지 않으면 [1,2],[1,3]이렇게 뽑고 싶은데
          //[1,2,3]이렇게 되기에 [1,2]일떄 2를 pop으로 제거하고 [1]로 만들어준후
            // for을 다시 돌려주여 [1,3]이 되도록 만들어 준다. 
            seq.pop();
            visited[i]=false
        }
    }
  }
  dfs(0)
    return result;
}

console.log(solution(n,m));