[JavaScript/node.js] 백준 3980번 - 선발 명단

[문제]

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

3980번: 선발 명단

 

[풀이]

단순히 DFS를 통해 선수 배치가 가능한 모든 조합을 완전 탐색하는 문제였습니다.

 

1. position 배열에 각 선수들의 가능한 포지션과 능력을 저장합니다.

• position의 i번째 배열에 [가능한 포지션, 능력] 형태로 push합니다.

따라서 예제의 position 정보를 모두 저장하면 다음과 같습니다.

[
  [ [ 0, 100 ] ],
  [ [ 1, 80 ], [ 2, 70 ], [ 3, 70 ], [ 4, 60 ] ],
  [ [ 1, 40 ], [ 2, 90 ], [ 3, 90 ], [ 4, 40 ] ],
  [ [ 1, 40 ], [ 2, 85 ], [ 3, 85 ], [ 4, 33 ] ],
  [ [ 1, 70 ], [ 2, 60 ], [ 3, 60 ], [ 4, 85 ] ],
  [ [ 5, 95 ], [ 6, 70 ], [ 7, 60 ], [ 8, 60 ] ],
  [ [ 1, 45 ], [ 5, 80 ], [ 6, 90 ], [ 7, 50 ], [ 8, 70 ] ],
  [ [ 5, 40 ], [ 6, 90 ], [ 7, 90 ], [ 8, 40 ], [ 9, 70 ] ],
  [ [ 6, 50 ], [ 7, 70 ], [ 8, 85 ], [ 9, 50 ] ],
  [ [ 6, 66 ], [ 7, 60 ], [ 9, 80 ], [ 10, 80 ] ],
  [ [ 6, 50 ], [ 7, 50 ], [ 9, 90 ], [ 10, 88 ] ]
]

 

2. DFS를 통해 11명의 포지션을 선택하고 각 능력의 합을 더해줍니다.

• visit배열을 통해 이미 선택된 포지션 값을 관리합니다.
• 만약 11번째 선수까지 포지션을 등록하면 DFS을 return합니다. (0~10번 선수를 모두 등록하고 idx 11일 때)

따라서 능력치 합의 최대를 구하면 970이 됩니다.

 

[코드]

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';

const input = fs.readFileSync(filePath).toString().split('\n');

const [C] = input[0].split(" ").map(Number);

let max = 0;

const dfs = (position, idx, visit, total) => {
    if(idx === 11) {
        if(total > max) {
            max = total;
        }
        return;
    }

    position[idx].forEach(element => {
        const [i, score] = element;
        if(!visit[i]) {
            visit[i] = true;
            dfs(position, idx + 1, visit, total + score);
            visit[i] = false
        }
    });
}

const setPosition = (position) => {
    const visit = Array.from({length: 11}, () => false);
    dfs(position, 0, visit, 0);
}

for(let i=0;i<C;i++) {
    const position = Array.from({length: 11}, () => []);
    max = 0;
    for(let j=0;j<11;j++) {
        const temp = input[11*i+1 + j].split(" ").map(Number);
        for(let k=0;k<11;k++) {
            if(temp[k] > 0) {
                position[j].push([k, temp[k]]);
            }
        }
    }
    setPosition(position);
    console.log(max);
}