https://school.programmers.co.kr/learn/courses/30/lessons/92342
DFS(깊이 우선 탐색)를 통해 경우의 수를 탐색하여 점수 차이를 최대로 만드는 라이언의 화살 배열을 반환하는 문제입니다.
DFS 탐색을 시작합니다.
현재 깊이에서 화살을 쏠 수 있다면 (info[v] < n), 다음 깊이로 이동하고 남은 화살 수를 갱신합니다.
현재 인덱스의 화살을 쏘지 않는 경우에도 다음 깊이로 이동하며 화살 개수를 유지합니다.
모든 화살을 쏜 경우에는 남은 화살이 있는지 확인하고, 남은 화살이 있다면 마지막 화살에 남은 화살 수를 저장합니다.
점수 차이를 계산하여 라이언이 어피치보다 점수를 더 많이 얻은 경우를 판별합니다.
현재까지의 최대 점수 차이보다 큰 경우, 최대 점수 차이를 갱신하고 결과 배열을 업데이트합니다.
최대 점수 차이가 같은 경우, 낮은 점수에 더 많은 화살을 쏜 경우를 결과 배열로 업데이트합니다.
최종적으로 업데이트된 결과 배열을 반환합니다.
/**
* 프로그래머스 양궁대회 (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; // 결과 반환
}
}