문제

N이 주어졌을 때, 1부터 N까지의 수로 이루어진 순열을 사전순으로 출력하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 8)이 주어진다.

출력

첫째 줄부터 N!개의 줄에 걸쳐서 모든 순열을 사전순으로 출력한다.

예제 입력

3

예제 출력

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

내가 했던 풀이 방법

1. checked 배열을 N크기로 만들고, 모두 false로 추기화한다.
2. sequence와 permutation 배열을 []로 초기화한 뒤, DFS를 depth를 0으로 주고 실행한다.
3. DFS 함수에서는 0부터 N-1까지 반복문으로 돌며, checked가 false일 경우, permutation에 현재 i값에 1을 더한 값을 넣어주고, checked를 true로 바꿔준다. 그 뒤, DFS의 depth를 1증가시켜 호출한다.
4. DFS가 재귀로 계속 호출되며, depth가 N이 될 때 permutation에 들어있는 요소를 공백을 추가하여 문자열로 바꿔준다.
5. 재귀가 끝날 때마다 permutation에 마지막 값을 하나씩 제거해주고, 해당 값에 대한 checked를 false로 바꾸어준다.

코드

const fs = require('fs');
let N = fs.readFileSync(0, 'utf-8').toString().trim();

N = parseInt(N);
let checked = Array.from({ length: N }, () => false);
let sequence = [];
let permutation = [];

DFS(0);

console.log(sequence.toString().replaceAll(',', '\n'));

function DFS(depth) {
  if (depth === N) {
    sequence.push(permutation.slice().join(' '));
    return;
  }

  for (let i = 0; i < N; i++) {
    if (!checked[i]) {
      permutation.push(i + 1);
      checked[i] = true;
      DFS(depth + 1);
      permutation.pop();
      checked[i] = false;
    }
  }
}

회고

이전에 백트래킹 문제를 풀게 됐는데 백트래킹을 정말 오랜만에 풀어 기억이 완전 소각되었기도 했고, 아직 자바스크립트로 자료구조/알고리즘을 구현하기엔 부족한 지식들이 많아서 이 부분들을 다시 공부한 뒤에 이와 관련된 문제들을 풀어야겠다고 생각했다. (덱이라던가...DFS...등등등) 그러다가 오늘 백트래킹 문제를 또 만나게 됐는데 더는 미루면 안되겠다 싶어서 풀어보게 되었다. 빨리 자료구조랑 알고리즘을 다시 복습해서 더 어려운 문제들을 풀어서 익숙해지게 만들어야겠다. 이런 간단한 백트래킹을 구현하는데에도 버벅이던게 좀 많았던 것 같다...