12869번: 뮤탈리스크

문제

스타크래프트 게임에서 뮤탈리스크 1마리가 SCV N대(최대 3대)를 공격하여 모두 파괴하려고 합니다. 뮤탈리스크는 한 번의 공격으로 3개의 타겟에 각각 9, 3, 1의 데미지를 입힐 수 있습니다. SCV들의 체력이 주어졌을 때, 모든 SCV를 파괴하기 위한 최소 공격 횟수를 구하는 문제입니다.

• 입력: 첫째 줄에 SCV의 수 N (1 ≤ N ≤ 3), 둘째 줄에 각 SCV의 체력(1 이상 60 이하의 정수)이 주어집니다.
• 출력: 모든 SCV를 파괴하기 위한 최소 공격 횟수를 출력합니다.

링크: https://www.acmicpc.net/problem/12869

풀이: 3차원 방문 배열을 이용한 탐색 최적화 (메모이제이션)

SCV가 최대 3대이므로, 각 SCV의 남은 체력을 3차원 배열의 인덱스로 활용하여 탐색 상태를 기록할 수 있습니다. DFS(깊이 우선 탐색)로 6가지 공격 패턴을 모두 시도하되, 동일한 상태를 반복 탐색하지 않도록 가지치기하는 것이 핵심입니다.

1. 음수 체력 보정: 공격을 받아 체력이 0 이하로 떨어질 수 있습니다. 3차원 배열의 인덱스 에러를 방지하고, 체력이 0 이하인 상태를 통일하여 처리하기 위해 탐색 시작 직후 Math.max(0, 체력)을 사용하여 음수를 0으로 보정해 줍니다.
2. 가지치기 (Pruning): 현재 탐색 중인 공격 횟수(cnt)가 이미 찾아낸 최소 정답(ans)보다 크거나 같다면, 가망이 없는 경로이므로 바로 탐색을 멈춥니다.
3. 상태 기록 및 중복 탐색 방지 (메모이제이션): d[a][b][c] 배열에 해당 체력 상태에 도달하기까지 걸린 최소 공격 횟수를 기록합니다. 만약 현재 탐색 중인 공격 횟수(cnt)가 이전에 동일한 상태에 도달했을 때 기록된 공격 횟수보다 크거나 같다면, 더 이상 탐색할 필요가 없는 비효율적인 경로이므로 즉시 return 하여 탐색을 중단합니다.
4. 공격 패턴 재귀 호출: 기록을 마친 뒤, 9, 3, 1의 데미지를 배분하는 6가지 순열 패턴에 대해 재귀적으로 함수를 호출하여 시뮬레이션을 이어갑니다. 모든 체력이 0이 되는 시점에 도달하면 최소 횟수를 갱신합니다.

코드

import java.io.*;
import java.util.*;

public class Main {
    static int ans = Integer.MAX_VALUE;
    // 3대의 SCV 체력을 인덱스로 하여 최소 공격 횟수를 기록할 3차원 배열
    static int[][][] d = new int[61][61][61];

    public static void main(String[] args) throws IOException {
       BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
       BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

       int n = Integer.parseInt(br.readLine());
       int[] a = new int[3]; 
       StringTokenizer st = new StringTokenizer(br.readLine());
       for (int i = 0; i < n; i++) {
          a[i] = Integer.parseInt(st.nextToken());
       }

       // DFS 탐색 시작 (초기 공격 횟수 0)
       go(0, a[0], a[1], a[2]);

       bw.write(ans + "");

       bw.flush();
       bw.close();
       br.close();
    }

    static void go(int cnt, int a, int b, int c) {
       // 1. 배열 인덱스 초과를 막기 위해 음수 체력을 0으로 보정
       a = Math.max(0, a);
       b = Math.max(0, b);
       c = Math.max(0, c);

       // 2. 이미 찾은 정답보다 횟수가 많거나 같다면 탐색 중단
       if (ans <= cnt) {
          return;
       }

       // 3. 모든 SCV가 파괴되었다면 최소 공격 횟수 갱신 후 종료
       if (a == 0 && b == 0 && c == 0) {
          ans = Math.min(ans, cnt);
          return;
       }

       // 4. 이전에 같은 체력 상태에 도달한 적이 있고, 그때의 공격 횟수가 현재보다 적거나 같다면 탐색 중단
       if (d[a][b][c] != 0 && d[a][b][c] <= cnt) {
          return;
       }

       // 현재 체력 상태에 도달하기 위한 최소 공격 횟수 기록
       d[a][b][c] = cnt;

       // 5. 9, 3, 1 데미지를 분배하는 6가지 모든 경우의 수에 대해 재귀 탐색
       go(cnt + 1, a - 9, b - 3, c - 1);
       go(cnt + 1, a - 9, b - 1, c - 3);
       go(cnt + 1, a - 3, b - 9, c - 1);
       go(cnt + 1, a - 3, b - 1, c - 9);
       go(cnt + 1, a - 1, b - 9, c - 3);
       go(cnt + 1, a - 1, b - 3, c - 9);
    }
}

알고리즘 분류

다이나믹 프로그래밍 (DP), 그래프 탐색, 너비 우선 탐색 (BFS), 깊이 우선 탐색 (DFS)