[백준_15649] N과 M(1) [ 백트래킹(기초) - 자바스크립트 )

문제

https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

 

How to Solve ?

 

[1] 왜 백트래킹을 사용하는가?

 

둘의 차이를 한 마디로 정리하라면, 불 필요한 방문을 줄이는 것인데요 ! N과 M 문제에서 우리에게 원하는건 "중복 되는 수열" 이 존재 하지 않는 것 입니다.

 

즉, [1,1] [2,2] [3,3] 와 같은 수열의 출력을 막아야 하는데 이것이 우리가 이 문제에 백트래킹을 적용 해야 하는 이유입니다.

 

[2] 어떻게 막는데?

 

1을 기준으로 dfs를 하게 될 때, 이를 방문 처리함으로써 ! [1,2,1] 과 같은 수가 나올 수 없도록 막고 자신의 순서가 끝나면 방문을 해제하는 식으로 구현 하였습니다.

 

function dfs(cnt) {
  if (cnt === M) {
    result += `${output.join(" ")}\n`;
    return;
  }

  for (let i = 1; i <= N; i++) {
    if (visited[i] === 1) continue;

    visited[i] = 1;
    output.push(i);
    dfs(cnt + 1);

    output.pop(); // 1 -> 2 -> 3 -> 4
    visited[i] = 0;
  }
}

let result = "";
const [N, M] = [4, 3];
const visited = Array(N + 1).fill(0);
const output = [];

dfs(0);
console.log(result.trim());