[백준 14889번] 브루트포스 알고리즘 - 스타트와 링크

✨ 문제 ✨

✨ 정답 ✨

const { notDeepEqual } = require("assert");
const { count } = require("console");
const fs = require("fs");
const { nextTick } = require("process");
const { start } = require("repl");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./예제.txt";
let input = fs.readFileSync(filePath).toString().trim().split('\n');


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

const N=+input.shift();
let scoreArray=[]
for (let i=0;i<N;i++){
    scoreArray.push(input[i].split(' ').map((el)=>+el))
}

let players=[];
for (let i=0;i<N;i++){
    players.push(i)
}

let startTeam=[];
let linkTeam=[];
const playerNumber=Math.floor(N/2);

const visited=new Array(N).fill(false);

let min=Number.MAX_SAFE_INTEGER;

const calculate=(team)=>{
    let sum=0;
    for (let i=0;i<team.length;i++){
        for (let j=0;j<team.length;j++){
            if (i===j){
                continue;
            }
            sum+=scoreArray[team[i]][team[j]]
        }
    }
    return sum;
}

const getLink=(players, startTeam)=>{
    let link=[];
    for (let i=0;i<players.length;i++){
        if (!startTeam.includes(players[i])){
            link.push(players[i]);
        }
    }
    return link;
}

const DFS=(count,restIndex)=>{
    if (count===playerNumber){
       linkTeam=getLink(players, startTeam);
       let startSum=calculate(startTeam);
       let linkSum=calculate(linkTeam);
       min=Math.min(Math.abs(startSum-linkSum), min);
       return;
    }
    for (let i=restIndex;i<N;i++){
        if (visited[i]){
            continue;
        }
        visited[i]=true;
        startTeam.push(i);
        DFS(count+1,i);
        startTeam.pop();
        visited[i]=false;
    }
}


DFS(0,0);
console.log(min);

🧵 참고한 정답지 🧵

https://kimbangg.tistory.com/206

💡💡 기억해야 할 점 💡💡