[BOJ] 3980 - 선발 명단 (Python, JavaScript)

 

 

아이디어

 

DFS과 백트래킹으로 남은 포지션에 선수들을 채워 나가며 능력치 합의 최댓값을 찾는다.

 

 

풀이 #1 (Python)

 

각각의 테스트 케이스에 대해 선수들의 능력치를 리스트 S에 입력 받는다.

메모리 절약과 DFS에서 빠른 접근을 위해 능력치가 0이 아닌 선수들만 인덱스와 능력치를 추가해 나간다.

포지션 할당 표시를 위해 0으로 채워진 리스트 visited를 생성하고 함수 dfs를 호출한다.

 

함수 dfs에서는 차례로 i 번째 선수를 적합한 포지션 중 남은 포지션에 배치하여 할당 표시 후,

현재 선수의 능력치 a를 능력치 합 total에 더하여 다음 선수로 함수를 재귀 호출한다.

배치가 끝나면 결과값 res와 능력치 합 total을 비교해 결과값을 능력치 합의 최댓값으로 갱신해 나간다.

 

import sys

input = sys.stdin.readline

def dfs(i, total):
    global res
    if i < 11:
        for j, a in S[i]:
            if visited[j] == 0:
                visited[j] = 1
                dfs(i+1, total+a)
                visited[j] = 0
    elif total > res:
        res = total

C = int(input())
for c in range(C):
    S = []
    for i in range(11):
        S.append([])
        temp = list(map(int, input().split()))
        for j in range(11):
            if temp[j]:
                S[-1].append((j, temp[j]))
    res = 0
    visited = [0]*11
    dfs(0, 0)
    print(res)

 

 

 

풀이 #2 (JavaScript)

 

풀이 #1과 같은 방식으로 동작한다.

선수들 능력치 배열 S, 결과값 저장 변수 res, 포지션 할당 표시 배열 visited를 for문 밖에서 선언한다.

 

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

function dfs(i, total) {
    if (i < 11) {
        for (let [j, a] of S[i]) {
            if (visited[j] == 0) {
                visited[j] = 1;
                dfs(i+1, total+a);
                visited[j] = 0;
            }
        }
    }
    else if (total > res) res = total;
}

const C = Number(input[0]);
let S, res, visited;
for (let c=0; c<C; c++) {
    S = [];
    for (let i=0; i<11; i++) {
        S.push([])
        temp = input[c*11+i+1].split(' ').map(Number);
        for (let j=0; j<11; j++) {
            if (temp[j]) S[i].push([j, temp[j]])
        }
    }
    res = 0;
    visited = Array(11).fill(0);
    dfs(0, 0);
    console.log(res);
}