백준 10974번 모든 순열 Node.js 풀이

문제 링크

- 풀이

const fs = require("fs");
const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const N = Number(input);

let visited = Array(N).fill(false);

let selected = Array(N).fill(0);

let answer = "";

function dfs(depth) {
  if (depth === N) {
    let result = [];
    for (let i = 0; i < N; i++) {
      result.push(selected[i]);
    }

    answer += result.join(" ") + "\n";
  }

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

    selected[depth] = i;
    visited[i] = true;
    dfs(depth + 1);
    visited[i] = false;
  }
}

dfs(0);

console.log(answer.trim());

여기서 visited는 방문처리 체크를 위한 배열

selected는 선택한 원소를 직접 넣어주기 위한 배열이다.

여기서 depth는 트리구조로 생각해보면 깊이를 의미하는것인데, 숫자로 따져보면 1 2 3 일때 깊이가 0이면 1, 1일때 2, 2일때 3이 된다.

  for (let i = 1; i <= N; i++) {
    // 방문처리가 되었다면 생략해준다.
    if (visited[i]) {
      continue;
    }

    // 선택한 원소를 넣어준다.
    selected[depth] = i;

    // 방문처리를 해준다.
    visited[i] = true;

    // 다음 깊이(숫자)로 넘어간다.
    dfs(depth + 1);

    // 방문처리를 해제해준다.
    visited[i] = false;
  }

여기서 반복문을 돌면서, 깊이 탐색을 해준다.

만약에 1이 들어갔다면 selected원소에 1을 넣어주고, 그 후에 2, 3 이런식으로 깊이 탐색을 하는것이다.

깊이 끝까지 다다르면 문자열을 합쳐주어서 answer에 더해준다.