[백준] 12869 뮤탈리스크 - JAVA

문제

뮤탈리스크

풀이

3개의 SCV에 공격을 하는 경우의 수는 6가지이다.
이 6가지로 나올 수 있는 공격을 dfs로 구하고 공격해서 남은 scv의 체력들이 0이 될때까지 반복해준다.

여기서 scv들의 체력들을 인덱스로 가지는 3차원 배열을 만들고
해당 3차원 배열의 값으로는 scv가 해당 체력까지 온 횟수를 저장해 준다.

예를들어 scv의 체력이 각각 3, 4, 1이고 3, 4, 1이 될때까지 공격 횟수가 3번이라면 dp[3][4][1] = 3 이 될것이다.

이것을 저장하는 이유는 dfs를 돌때 해당 공격 횟수의 값이 dp에 저장된 공격 횟수보다 크다면 어차피 최솟값이 될 수 없으므로 return을 해주기 위함이다.

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
  static int[] scvs;
  static int[][] pattern = {{-9,-3,-1},{-9,-1,-3},{-3,-9,-1},{-3,-1,-9},{-1,-3,-9},{-1,-9,-3}};
  static int[][][] dp = new int[61][61][61];
  static int minCnt = Integer.MAX_VALUE;
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int N = Integer.parseInt(st.nextToken());
    scvs = new int[3];
    st = new StringTokenizer(br.readLine());
    for(int i=0; i<N; i++) {
      scvs[i] = Integer.parseInt(st.nextToken());
    }
    dfs(scvs, 0);
    System.out.println(minCnt);
  }
  public static void dfs(int[] scv,int cnt) {
    if(minCnt <= cnt) return;
    if(dp[scv[0]][scv[1]][scv[2]] != 0 && dp[scv[0]][scv[1]][scv[2]] <= cnt) return;
    dp[scv[0]][scv[1]][scv[2]] = cnt;

    if(scv[0] == 0 && scv[1] == 0 && scv[2] == 0) {
      minCnt = Math.min(minCnt, cnt);
      return;
    }

    for(int i=0; i<6; i++) {
      dfs(new int[] {Math.max(scv[0]+pattern[i][0], 0),Math.max(scv[1]+pattern[i][1], 0),Math.max(scv[2]+pattern[i][2], 0)},cnt+1);
    }
  }
}