백준 12869 - 뮤탈리스크

Java

12869 번 - 뮤탈리스크

문제

접근 방법

SCV 입력 받기

우선 문제의 조건에 scv는 최소 1마리 부터 3마리까지 들어 올 수 있다.
따라서 크기가 3인 int형 배열을 선언하여 받는다.
이는 SCV 1마리나 2마리를 받아도 남은 빈자리는 체력이 0이므로 죽은 것으로 간주하면 된다.

뮤탈리스크의 공격

뮤탈리스크는 총 3번을 공격하며, 각각 체력 9, 3, 1을 깎는다.
이를 순열로 나열하면 총 6가지가 나오는데, 각 경우마다 6가지의 공격을 하여 DFS를 통해 재귀로 모든 경우의 수를 탐색한다.

DP

위의 방법으로만 계산하면 시간 초과가 나올 것으로 예상된다.
따라서 3차원 DP를 두어, 각 SCV의 체력까지 도달하는데 걸리는 뮤탈리스크의 공격을 저장한다.
이후 이전과 똑같은 SCV 3개의 체력으로 새로운 함수를 호출 하였을 때, 이전의 공격 횟수보다 현재 도달하는데 걸린 횟수가 같거나 더 크다면 더 이상 탐색할 필요가 없으므로 종료하는 방식으로 Back-Tracking을 한다.

따라서, 문제의 핵심이 되는 코드는

if(dp[a][b][c] <= cnt && dp[a][b][c] != 0) {
	return;
}

이다.

코드

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

public class Main {
	static int n, result = Integer.MAX_VALUE;
	static int[][][] dp;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    	
    	n = stoi(br.readLine());
    	StringTokenizer stk = new StringTokenizer(br.readLine());
    	
    	dp = new int[61][61][61];
    	int[] arr = new int[3];
    	for(int i = 0; i < n; i++) {
    		arr[i] = stoi(stk.nextToken());
    	}
    	
    	DFS(arr,0);
    	System.out.println(result);
    	
    	br.close();
	}
	
	static int[] arrA = {9,9,3,3,1,1};
	static int[] arrB = {3,1,9,1,9,3};
	static int[] arrC = {1,3,1,9,3,9};
	
	static void DFS(int[] arr, int cnt) {
		int a = arr[0];
		int b = arr[1];
		int c = arr[2];
		// 한번 방문한 상태에서 현재 수 보다 dp로 저장한 수가 더 작은 경우 
		if(dp[a][b][c] <= cnt && dp[a][b][c] != 0) {
			return;
		}
		// 종료 조건
		if(a == 0 && b == 0 && c == 0) {
			result = Math.min(result, cnt);
			return;
		}
		dp[a][b][c] = cnt;
		
		// 뮤탈리스크가 공격 할 수 있는 모든 경우의 수를 따진다.
		int nA, nB, nC;
		for(int i = 0; i < 6; i++) {
			nA = a - arrA[i];
			nB = b - arrB[i];
			nC = c - arrC[i];
			if(nA < 0) nA = 0;
			if(nB < 0) nB = 0;
			if(nC < 0) nC = 0;
			DFS(new int[] {nA, nB, nC}, cnt + 1);
		}
	}
	
	
	static int stoi(String str) {
    	return Integer.parseInt(str);
    }
}

총평

후기

처음에 dp로 백트래킹을 할 때 한번 방문 했으면 바로 return하게 하였다.
이는 이후에 도달한 경우에서 더 단축 된 경우가 있을 수 있으므로 이전 DP와 현재 cnt를 비교하는 방법으로 백 트래킹을 수행하여야 한다.

개선할 점