코딩테스트 - 백트래킹

개념

모든 경우의 수를 확인해야할 때

• for로는 확인 불가한 경우 ( 깊이가 달라질 때)

문제 15649

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

ex)
input:
4 2

output:
1 2
1 3
1 4
2 1
2 3
2 4
3 1
3 2
3 4
4 1
4 2
4 3

//백트래킹

/*
1. 아이디어
    - 백트래킹 재귀함수 안에서,  for 돌면서 숫자 선택(방문여부 확인)
    - m의 조건이면 print
2. 시간복잡도
    - 중복없으므로 N! = 최대 10까지
3. 자료구조
    - 방문여부 = int[]
    - 결과값 = int[]
    - 입력값 = N,M
*/

const readline = require("readline");

const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const input = [];

rl.on("line", function (line) {
  input.push(line);
}).on("close", () => {
  const [N, M] = input[0].split(" ").map(Number);
  const visit = [];
  for (let i = 0; i < N + 1; ++i) {
    visit.push(false);
  }
  const res = [];

  function recur(num) {
    //m과 일치할때
    if (num == M) {
      console.log(res.join(" "));
      return;
    }

    for (let i = 1; i < N + 1; ++i) {
      //방문하지 않았으면
      if (visit[i] == false) {
        visit[i] = true;
        res.push(i);
        recur(num + 1);
        //되돌아가는 과정이 필요하다
        visit[i] = false;
        res.pop();
      }
    }
  }

  recur(0);
});

알아야할것

• 백트래킹은 N이 작다
• 중복가능할경우 N^N이므로 최대 8개
• 중복불가능할경우 N! 이므로 최대 10개
• 재귀함수 사용할 때는 종료 시점을 잊지 말아야 한다