BOJ 14889 스타티와 링크(JS)

https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

 

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = fs.readFileSync(filePath).toString().trim().split("\n");
const n = Number(input.shift());
const arr=[];
for(let i=0; i<n; i++){
    const num = input.shift().split(" ").map(Number);
    arr.push(num);
}


let min = Infinity;
let isused = Array(n).fill(0);

function dfs(index, isused, k) {
  if (index === Number(n / 2)) {
    let start=[];
    let link=[];
    let StartTeam=[];
    let LinkTeam=[];
    let StartScore=0;
    let LinkScore=0;

    for(let i=0; i<isused.length; i++){
        if(isused[i]){
            start.push(i);
        }
        else{
            link.push(i);
        }
    }

    for(let i=0; i<start.length; i++){
        for(let j=i+1; j<start.length; j++){
                StartTeam.push([start[i],start[j]]);
        }
    }
    
    for(let i=0; i<link.length; i++){
        for(let j=i+1; j<link.length; j++){
            LinkTeam.push([link[i],link[j]]);
        }
    }

    for(let i=0; i<StartTeam.length; i++){
        const [x,y] = StartTeam[i];
        StartScore += arr[x][y];
        StartScore += arr[y][x];
    }

    for(let i=0; i<LinkTeam.length; i++){
        const [x,y] = LinkTeam[i];
        LinkScore += arr[x][y];
        LinkScore += arr[y][x];
    }

    result=Math.abs(StartScore-LinkScore);

    min = Math.min(min, result);
  }




  for (let i = k; i < n; i++) {
    if (!isused[i]) {
      isused[i] = 1;
      dfs(index + 1, isused, k);
      isused[i]=0;
    }
  }

}

dfs(0, isused, 0);

console.log(min);

이렇게 풀었더니 답은 나오는데 시간초과..

나름 backtracking을 이용했지만 점수 구하는 과정에서 배열을 너무 많이 돌려서 인지 아니면 백트래킹이 잘못되었는지 알아보니..

백트래킹에서 중복이 되고 있어서 고쳤음..

 

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const input = fs.readFileSync(filePath).toString().trim().split("\n");
const n = Number(input.shift());
const arr=[];
for(let i=0; i<n; i++){
    const num = input.shift().split(" ").map(Number);
    arr.push(num);
}


let min = Infinity;
let isused = Array(n).fill(0);

function dfs(index, isused, k) {
  if (index === Number(n / 2)) {
    let start=[];
    let link=[];
    let StartTeam=[];
    let LinkTeam=[];
    let StartScore=0;
    let LinkScore=0;
    for(let i=0; i<isused.length; i++){
        if(isused[i]){
            start.push(i);
        }
        else{
            link.push(i);
        }
    }

    
    for(let i=0; i<start.length; i++){
        for(let j=i+1; j<start.length; j++){
            StartTeam.push([start[i],start[j]]);
        }
    }
    
    for(let i=0; i<link.length; i++){
        for(let j=i+1; j<link.length; j++){
            LinkTeam.push([link[i],link[j]]);
        }
    }


    for(let i=0; i<StartTeam.length; i++){
        const [x,y] = StartTeam[i];
        StartScore += arr[x][y];
        StartScore += arr[y][x];
    }

    for(let i=0; i<LinkTeam.length; i++){
        const [x,y] = LinkTeam[i];
        LinkScore += arr[x][y];
        LinkScore += arr[y][x];
    }

    result=Math.abs(StartScore-LinkScore);

    min = Math.min(min, result);
  }




  for (let i = k; i < n; i++) {
    if (!isused[i]) {
      isused[i] = 1;
      dfs(index+1, isused, i);
      isused[i]=0;
    }
  }

}

dfs(0, isused, 0);

console.log(min);

그랬더니 맞았음..!
사실 백트래킹이나 재귀dfs문제 들이 너무너무 어려워서 고민도 거의 안하고 문제를 풀어왔는데 뭔가 오래걸려도 할 수 있을 것 같아서 풀어보니 가능 하다는걸 깨달았다..

여전히 재귀는 어렵다..!