문제
알파-베타 가지치기는 미니맥스와 같은 답을 내면서 결과를 바꿀 수 없는 가지를 건너뜁니다. 두 경계를 추적하는데, alpha는 MAX가 이미 확보한 최선의 점수이고 beta는 MIN이 이미 확보한 최선의 점수입니다.
게임 트리는 완전 트리입니다. 모든 내부 노드는 branching개의 자식을 가지고, 모든 리프는 같은 깊이에 있습니다. leaves는 리프 점수를 왼쪽에서 오른쪽으로 나열합니다. 루트는 MAX 노드이고 층은 MAX, MIN, MAX, … 순서로 번갈아 나옵니다.
alpha = -∞, beta = +∞에서 시작해 자식을 왼쪽에서 오른쪽으로 탐색합니다.
- MAX 노드에서는 각 자식 다음에 best = max(best, value), 그다음 alpha = max(alpha, best).
- MIN 노드에서는 각 자식 다음에 best = min(best, value), 그다음 beta = min(beta, best).
- alpha ≥ beta가 되는 즉시 그 노드의 나머지 자식을 건너뜁니다.
alpha_beta(leaves, branching)를 구현하세요.
입력
leaves: 왼쪽에서 오른쪽으로의 리프 점수. 길이는 branching의 거듭제곱입니다.
branching: 내부 노드당 자식 수.
출력
[value, evaluated]를 반환합니다. 루트의 미니맥스 값과 평가한 리프 수입니다.
제약 조건
2 ≤ branching ≤ 5, leaves 길이 = branching^depth (1 ≤ depth ≤ 8), 리프는 최대 10,000개
-1,000 ≤ 각 리프 ≤ 1,000
예시
입력:
leaves = [3, 12, 8, 2, 4, 6, 14, 5, 2]
branching = 3
예상 출력:
expected = [3, 7]입력:
std::vector<long long> leaves = {3, 12, 8, 2, 4, 6, 14, 5, 2};
long long branching = 3;
예상 출력:
std::vector<long long> expected = {3, 7};입력:
long[] leaves = new long[] {3, 12, 8, 2, 4, 6, 14, 5, 2};
long branching = 3;
예상 출력:
long[] expected = new long[] {3, 7};설명
첫 번째 MIN 노드는 3, 12, 8을 보고 3을 반환하므로 alpha = 3입니다. 두 번째 MIN 노드는 2를 보고 beta = 2 ≤ alpha가 되어 4와 6을 건너뜁니다. 세 번째는 14, 5, 2를 보고 2를 반환합니다. 루트 값은 max(3, 2, 2) = 3이며, 9개 중 7개의 리프를 확인했습니다.
입력:
leaves = [5, 6, 7, 4]
branching = 2
예상 출력:
expected = [5, 4]입력:
std::vector<long long> leaves = {5, 6, 7, 4};
long long branching = 2;
예상 출력:
std::vector<long long> expected = {5, 4};입력:
long[] leaves = new long[] {5, 6, 7, 4};
long branching = 2;
예상 출력:
long[] expected = new long[] {5, 4};설명
왼쪽 MIN 노드는 5와 6을 평가하고 5를 반환하므로 alpha = 5입니다. 오른쪽 MIN 노드는 7 (beta = 7), 다음으로 4 (beta = 4 ≤ 5)를 평가합니다. 리프 4개가 모두 평가되고 값은 5입니다.
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.