[코딩테스트] 백준 - 10819번 차이를 최대로 DFS (JS)

문제설명

N개의 정수로 이루어진 배열 A가 주어진다. 이때, 배열에 들어있는 정수의 순서를 적절히 바꿔서 다음 식의 최댓값을 구하는 프로그램을 작성하시오.

|A[0] - A[1]| + |A[1] - A[2]| + ... + |A[N-2] - A[N-1]|

제한사항

첫째 줄에 N (3 ≤ N ≤ 8)이 주어진다. 둘째 줄에는 배열 A에 들어있는 정수가 주어진다. 배열에 들어있는 정수는 -100보다 크거나 같고, 100보다 작거나 같다.

첫째 줄에 배열에 들어있는 수의 순서를 적절히 바꿔서 얻을 수 있는 식의 최댓값을 출력한다.

문제풀이

배열 A를 순회하면서 각 요소마다 깊이 우선 탐색을 진행한다.
깊이 우선 탐색 시에는 이번 탐색 시 방문했던 요소는 제외하고 배열에 추가한다.
배열 길이가 N과 동일한 경우 현재 배열에 담긴 원소들로 식을 계산하고 이전 최대값보다 더 큰 경우 최대값을 갱신한다.

코드

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

const N = Number(input[0]);
const arr = input[1].split(' ').map(Number);
let answer = 0;
let visited = new Array(N).fill(false);
let list = [];
for(let i = 0 ; i < N; i++) {
  visited[i] = true;
  list.push(arr[i]);
  dfs();
  list.pop();
  visited[i] = false;
}

function dfs() {
  if(list.length === N) {
    calculator();
    return;
  }
  for(let i = 0 ; i < N; i++) {
    if(visited[i]) continue;
    visited[i] = true;
    list.push(arr[i]);
    dfs();
    list.pop();
    visited[i] = false;
  }
}

function calculator() {
  let sum = 0;
  for(let i = 0 ; i < N - 1; i++) {
    sum += Math.abs(list[i] - list[i + 1]);
  }
  answer = Math.max(answer, sum);
}

console.log(answer);