(프로그래머스 KAKAO JS)양궁대회

https://programmers.co.kr/learn/courses/30/lessons/92342

코딩테스트 연습 - 양궁대회

 

완전 탐색과 DFS로 풀이.

 

탐색을 모두 진행한 후 만약 score가 0이라면 라이언이 무조건 진 경우기 때문에 [-1]을 리턴.

그렇지 않으면 answer을 리턴한다.

 

우선 모든 경우를 탐색해야 하기 때문에 for문으로 10 ~ 0 점을 모두 쏘아봐야 한다.

단, 시작은 무조건 어피치가 쏜 화살보다 1개 많은 화살을 쏘고 DFS 탐색을 진행한다.

(화살의 갯수가 같은 경우 어피치가 점수를 가져가기 때문에, 무조건 라이언이 점수를 가져가는 경우로 시작)

for문에서 DFS를 호출할 때 넘겨주는 값은 (다음 화살을 맞힐 인덱스, 남은 화살의 개수, 현재 라이언의 과녁)이다.

 

DFS.

우선 종료 조건을 정의한다.

remain이 0보다 작은 경우는 진행하면 안되기 때문에 return.

만약 remain이 0인 경우 모든 화살을 쐈기 때문에 점수를 비교해야 한다.

 

서로의 과녁을 비교해 하나씩 비교한다.

각 점수의 화살 갯수가 0이 아닌 경우 점수차를 계산한다.

 

점수 차를 계산하여 현재 score와 비교한다.

만약 두 값이 같은 경우, 적은 점수를 더 많이 맞힌 과녁으로 answer을 교체한다.

(이 조건은 answer와 board를 reverse() 하여 join("")을 하고, 대소 비교를 통해 알아낼 수 있다.)

그렇지 않고, 현재 score가 더 작은 경우 answer을 board로 교체하고, score를 갱신한다.

 

만약 remain이 0이 아니라면 계속 화살을 쏜다.

for문은 현재 들어온 index ~ 0까지 반복한다.

화살을 쏘는 조건은 어피치가 쏜 화살의 갯수 + 1 ~ 0까지다.

(0까지 진행하는 이유는, DFS 탐색을 더 진행하여 낮은 점수를 더 많이 맞춘 경우를 고려하기 때문이다.)

 

위와 같은 조건으로 DFS에 인자를 넘겨주면 알아서 계산을 진행하여 답을 유추할 수 있다.

const solution = (n, info) => {
    let answer = [];
    let score = 0;
    
    const dfs = (index, remain, board) => {
        if(remain < 0){
            return;
        }
        
        if(remain === 0){
            let rScore = 0;
            let aScore = 0;
            
            for(let i = 0; i < 11; i++){
                if(info[i] === 0 && board[i] === 0){
                    continue;
                }
                
                const diff = info[i] - board[i];
                
                if(diff >= 0){
                    aScore += (10 - i);
                } else if(diff < 0){
                    rScore += (10 - i);
                }
            }
            
            const diff = rScore - aScore;
            
            if(score === diff){
                const aReverse = [...answer].reverse().join("");
                const bReverse = [...board].reverse().join("");
                
                if(aReverse < bReverse){
                    answer = [...board];
                }
            } else if(score < diff){
                answer = [...board];
                score = diff;
            }
                
            return;
        }
        
        for(let i = index; i < 11; i++){
            const origin = board[i];
            
            for(let j = info[i] + 1; j >= 0; j--){
                board[i] = j;
                dfs(i + 1, remain - j, board);
            }
            board[i] = origin;
        }
    }
    
    for(let i = 0; i < 11; i++){
        const board = Array(11).fill(0);
        
        board[i] = info[i] + 1;
        dfs(i + 1, n - board[i], board);
    }
    
    return score === 0 ? [-1] : answer;
}