[알고리즘] Java / 백준 / 뮤탈리스크 / 12869

[알고리즘] Java / 백준 / 뮤탈리스크 / 12869

문제

문제 링크

접근 방식

모든 scv 체력이 0이 될 때 까지 dfs로 뮤탈리스크의 6가지 공격 패턴으로 탐색한다

공격해서 남은 scv의 체력들을 기억하여 가지치기한다.

가지치기 조건은 다음과 같다.

1. 모든 scv가 죽으면 공격 횟수 최솟값을 갱신한다.
2. 이미 방문했을 때 현재의 공격 횟수 최솟값보다 이전이 더 적다면 중단한다.
3. 공격 횟수 최솟값보다 현재 공격 횟수가 크거나 같으면 중단한다.

코드

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

public class Main_12869 {
	
	static int[][] deltas = {{-9,-3,-1},{-9,-1,-3},{-3,-9,-1},{-3,-1,-9},{-1,-9,-3},{-1,-3,-9}};
	static int[][][] dp;
	static int min;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int N = Integer.parseInt(br.readLine());
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int[] scv = new int[3];
		
		for(int i=0;i<N;i++) {
			scv[i] = Integer.parseInt(st.nextToken());
		}
		
		dp = new int[61][61][61];
		min = Integer.MAX_VALUE;
		
		dfs(scv,0);
		
		System.out.println(min);
		
	}
	
	public static void dfs(int[] scv, int cnt) {
		
		int s1 = scv[0];
		int s2 = scv[1];
		int s3 = scv[2];
		
		// 공격 횟수 최솟값 보다 현재 공격 횟수가 같거나 클 경우 중단
		if(min <= cnt) return;
		
		// 이미 방문했는데 기존 공격 횟수가 더 작을 경우 중단
		if(dp[s1][s2][s3] != 0 && dp[s1][s2][s3] <= cnt) return;
		
		dp[s1][s2][s3] = cnt;
		
		// 모든 scv가 죽을 경우 최솟값 갱신 및 중단
		if(s1 == 0 && s2 == 0 && s3 == 0) {
			min = Math.min(min, cnt);
			return;
		}
		
		// 6가지 공격 패턴으로 현재 scv를 공격한 후 넘김
		for(int i=0;i<6;i++) {
			dfs(new int[] {Math.max(s1 + deltas[i][0], 0),Math.max(s2 + deltas[i][1], 0),Math.max(s3 + deltas[i][2], 0)}, cnt+1);
		}
	}

}