[백준] 15649. N과 M (1) (자바스크립트/javascript/js/node.js/백트래킹)

 

문제를 풀기 위한 아이디어

이 문제는 한마디로 순열을 구하는 것이다.

이전에 내가 포스팅했던 순열 알고리즘을 써도 되지만, 이 문제는 백트래킹 알고리즘 유형에 있던 문제이기 때문에 한번 백트래킹으로 풀어보았다.

 

* 백트래킹 이란 ?

모든 조합의 수를 다 살펴보되 (완전탐색) 단 조건이 만족할 때에만 탐색하는 방법을 말한다.

쉽게 말해 해를 찾는 도중 해가 아닌 것 같으면 되돌아가서 해를 찾는 것이다. 

완전탐색을 하는 방법으로는 DFS, BFS가 있다. 백트래킹은 DFS에서 효율적인 방법이다. 왜냐하면 DFS는 깊이 우선 탐색이므로 갈 수 있는 최대 깊이까지 갔다가 돌아온다. 우리는 끝까지 탐색하지 않아도 중간에 조건에 부합하지 않는 경우가 있어서 현재 경로가 잘못된 것임을 알 수 있는 경우가 종종 있다. 이런 알면서도 들어가는 비효율적인 경우를 "가지치기" 하기 위해 백트래킹이 사용되는 것이다.

→ 즉, 백트래킹은 DFS에 조건을 걸어놓고 조건에 부합하지 않으면 해당 가지는 거기서 더 이상 들어가지 않는 것이다.

 

이 문제에서는 N과 M은 최대 8까지 밖에 없다.

각 수마다 방문했는지 아닌지를 체크하는 visited 배열을 만들어 초기값으로 false를 넣어주고, 반복문을 돌면서 방문한 적이 없다면 array에 넣어주고, 재귀적으로 또 함수를 실행한다. 그렇게 실행하다가 count가 M과 같아진다면 출력하고 함수를 종료한다.

 

내가 작성한 코드 (자바스크립트)

const dfs = (cnt) => {
  if (cnt === M) {
    console.log(array.join(" "));
    return;
  }
  for (let i = 1; i <= N; i++) {
    if (!visited[i]) {
      visited[i] = true;
      array[cnt] = i;
      dfs(cnt + 1);
      visited[i] = false;
    }
  }
};

let fs = require("fs");
let input = fs
  .readFileSync("/dev/stdin")
  .toString()
  .trim()
  .split(" ")
  .map((element) => Number(element));
const N = input[0];
const M = input[1];
const visited = new Array(N + 1).fill(false);
const array = [];
dfs(0);