[프로그래머스 Level.2] 양궁대회 - DFS

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

솔루션

DFS(깊이 우선 탐색)를 통해 경우의 수를 탐색하여 점수 차이를 최대로 만드는 라이언의 화살 배열을 반환하는 문제입니다.

1. DFS 탐색을 시작합니다.

2. 현재 깊이에서 화살을 쏠 수 있다면 (info[v] < n), 다음 깊이로 이동하고 남은 화살 수를 갱신합니다.

3. 현재 인덱스의 화살을 쏘지 않는 경우에도 다음 깊이로 이동하며 화살 개수를 유지합니다.

4. 모든 화살을 쏜 경우에는 남은 화살이 있는지 확인하고, 남은 화살이 있다면 마지막 화살에 남은 화살 수를 저장합니다.

5. 점수 차이를 계산하여 라이언이 어피치보다 점수를 더 많이 얻은 경우를 판별합니다.

6. 현재까지의 최대 점수 차이보다 큰 경우, 최대 점수 차이를 갱신하고 결과 배열을 업데이트합니다.

7. 최대 점수 차이가 같은 경우, 낮은 점수에 더 많은 화살을 쏜 경우를 결과 배열로 업데이트합니다.

8. 최종적으로 업데이트된 결과 배열을 반환합니다.

소스코드

/**
 * 프로그래머스 양궁대회 (Level 2) - DFS
 * 문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/92342?language=java
 */
 class Solution {

    static int[] answer = {-1}; // 결과를 저장하는 배열

    static int[] shoot; // 라이언이 쏠 화살의 개수를 저장하는 배열

    static int maxDiffScore = Integer.MIN_VALUE; // 최대 점수 차이

    // 라이언의 점수 차이 계산 메소드
    public int calDiffScore(int[] info, int[] shoot) {
        int apeachScore = 0;
        int ryanScore = 0;

        // 각 라이언과 아프리카 거북이의 점수를 계산
        for (int i = 0; i < 11; i++) {
            if (info[i] == 0 && shoot[i] == 0) {
                continue; // 둘 다 맞추지 않은 경우 스킵
            }

            if (info[i] < shoot[i]) {
                ryanScore += (10 - i);
            } else {
                apeachScore += (10 - i);
            }
        }

        return ryanScore - apeachScore; // 라이언과 어피치의 점수 차이 반환
    }

    // DFS 탐색 메소드
    public void dfs(int v, int n, int[] info) {
        if (v == 11) { // 모든 화살을 쏜 경우
            if (n != 0) { // 남은 화살이 있는 경우
                shoot[10] = n; // 마지막 화살에 남은 화살 개수 저장
            }

            // 점수 차이 계산
            int diffScore = calDiffScore(info, shoot);

            // 라이언이 어피치보다 점수를 더 많이 얻은 경우
            if (diffScore <= 0) {
                return; // 탐색 종료
            }

            // 현재 최대 점수 차이보다 큰 경우
            if (maxDiffScore < diffScore) {
                maxDiffScore = diffScore; // 최대 점수 차이 갱신
                answer = shoot.clone(); // 결과 배열 업데이트
            } else if (maxDiffScore == diffScore) { // 최대 점수 차이가 같은 경우
                for (int i = 10; i >= 0; i--) {
                    if (answer[i] < shoot[i]) { // 더 많은 화살을 쏜 경우
                        answer = shoot.clone(); // 결과 배열 업데이트
                        return; // 탐색 종료
                    } else if (shoot[i] < answer[i]) return; // 더 적은 화살을 쏜 경우
                }
            }
            return;
        }

        // 현재 인덱스의 화살을 쏴야 하는 경우
        if (info[v] < n) {
            shoot[v] = info[v] + 1; // 라이언이 쏠 화살 개수 설정
            dfs(v + 1, n - (info[v] + 1), info); // 다음 인덱스로 이동하고 남은 화살 개수 갱신
        }

        shoot[v] = 0; // 현재 인덱스의 화살을 쏘지 않는 경우
        dfs(v + 1, n, info); // 다음 인덱스로 이동하고 화살 개수 유지
    }

    // 해결 함수
    public int[] solution(int n, int[] info) {
        shoot = new int[11]; // 라이언이 쏠 화살 개수를 저장하는 배열 초기화

        dfs(0, n, info); // DFS 탐색 시작

        return answer; // 결과 반환
    }
}