백준 14889) 스타트와 링크 node.js

문제

입력

첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

출력

첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

나의 풀이

나의 코드

const internal = require('stream');
const { CLIENT_RENEG_LIMIT } = require('tls');

let input = require('fs').readFileSync(__dirname+'/input.txt').toString().split('\n');  
var n = Number(input[0].split(' '));    //모인 사람의 수 


var arr = []
for ( let i = 1; i < n+1; i ++){
    arr.push(input[i].split(' '))
}

var answer =0
let min = 1000000

function solution(n, arr){

    let assi = Array.from({length:n}, ()=>0 )
    let ch = Array.from({length:n}, ()=> 0)
   

    function DFS(k){
        const set = new Set( assi )
        let an = [...set]   //중복제거
        let st = 0
        let lt = 0
        
        if(an.length === n){ //종료조건 
           for( let i =0 ; i <  an.length/2 ; i ++){ //an{1,2,3,/4,5,6}을 탐색
                for(let j = 0; j < an.length/2; j++){
                    st += Number(arr[an[i]][an[j]])
                }
           }

           for( let i = an.length/2; i <  an.length ; i ++){ //an{1,2,3,/4,5,6}을 탐색
            for(let j = an.length/2; j < an.length; j++){
                lt += Number(arr[an[i]][an[j]])
            }
         }

         answer = Math.abs(st-lt)
         if(min > answer ) min = answer
       
        }
       
        for ( let i =0 ; i < n ; i ++){
            if ( !ch[i]){
                assi[k] = i
                ch[i]=1 
                DFS(k+1)
                ch[i]=0
            }
        }

    }

    DFS(0)
    return min 
}


console.log(solution(n,arr))     

풀이

백트레킹을 사용해서 풀었다
모든 경우의 수를 다 구해야할 때 -> 백트래킹사용 -> 재귀사용 하면 된다

나는 스타트팀과 링크팀을 따로 구하지 않고
나올 수 있는 수열 N자리를 한번에 다 구했다 (백트래킹으로!)
그러면(만약 N이 0이라면) {0,0,0,0,0,0},{0,0,0,0,0,1} 이런식으로
안에 중복값이 생기기 때문에
Set이라는 중복을 제거해주는 메소드로 중복을 제거해줬다

그리고 중복을 제거하게 되면 length 가 6인 애들만 따로 모아주면 되는데
그 값이 바로 랜덤으로 만들어진 N자리의 값들!

나는 앞 N/2, 뒤 N/2 이렇게 스타트팀과 링크팀을 각각 구했다

if(an.length === N ) 이라면 팀 만들기는 종료하고
스타트팀과 링크팀의 차이를 구하면 되는데
나는 이 부분에서 문제가 너무 헷갈렸다 . . .

그럼 팀인원이 세명이면... Sijk 이렇게 되나? 하고 생각했었는데
그게 아니라 그 3명 안에서 두명씩 짝을 지은 걸 다 합해야했다!!!
(oh no.. ~~~)

그래서 만약 내가 구한 an 값이 {1,2,3,4,5,6} 이라면
1,2,3/ 4,5,6 이렇게 스타트/링크 로 나누고
startteam = (1,1)+(1,2)+(1,3)+(2,1)+(2,2)+...(3,3) 이렇게 말이다..!

여기서 헤매서 시간이 오래걸렸다 ㅎㅎㅎ 하지만 해결!
이중 for문을 돌아서 (1,1),(1,2)와 같은 조합들을 구하고
그 조합들로 문제에서 입력한 array에서 해당 시너지의 값을 추출해줬다

st와 lt를 구하고 그 차이를 절댓값으로 바꾼다음
min을 구해줬다 ! ! !

이것도 뿌듯했던 문제였다는~