[백준] 12869. 뮤탈리스크 (DP/Java)

[백준] 12869. 뮤탈리스크

 

📌 풀이 과정

처음엔 완전 탐색으로 풀 수 있겠지? 하는 생각에 풀었다가 시간 초과가 떴다.

알고리즘 유형을 확인해보니.... DP를 활용한 BFS 로직을 작성해야 함을 깨달았다...

기존 완탐으로 작성한 코드는 시간 초과!!!!

제출 코드

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

public class Main{

    static int N, min;
    static int[] SCV;
    static List<int[]> turns;
    static int[] power = {9, 3, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        turns = new ArrayList<>();
        SCV = new int[N];
        min = Integer.MAX_VALUE;

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

        pickTurn(new boolean[N], new int[N], 0);
        attack(SCV.clone(), 0);

        System.out.println(min);

    }


    private static void attack(int[] scv, int cnt){
        boolean allDead = true;
        for(int i = 0; i < N; i++){
            if(scv[i] > 0) { // 아직 살아있는 SCV가 있다.
                allDead = false;
                break;
            }
        }

        if(allDead){
            min = Math.min(cnt, min);
            return;
        }

        for(int[] turn : turns){
            int[] nextScv = scv.clone();

            for(int i = 0; i < turn.length; i++){
                if(nextScv[turn[i]] > 0) {  // 살아있는 SCV만 공격
                    nextScv[turn[i]] -= power[i];
                }
            }
            attack(nextScv, cnt + 1);
        }

    }

    private static void pickTurn(boolean[] picked, int[] numbers, int depth){
        if(depth == N){
            int[] result = numbers.clone();
            turns.add(result);
            return;
        }

        for(int i = 0; i < N; i++){
            if(picked[i]) continue;

            numbers[depth] = i;
            picked[i] = true;
            pickTurn(picked, numbers, depth + 1);
            picked[i] = false;

        }

    }

}

 

문제 조건

1. 뮤탈리스크는 한번에 3개의 SCV를 공격할 수 있다.

2. 공격 데미지는 9, 3, 1로 고정되어 있으며, 이 데미지를 순서를 바꿔가며 적용할 수 있다.

3. 목표는 모든 SCV를 파괴하는데 필요한 최소 공격 횟수를 구하는 것!!

 

해결 방법

BFS의 탐색 시간을 줄이기 위해 DP 개념을 활용해보자!

• BFS를 사용해 모든 가능한 공격 케이스를 탐색한다. -> 최소 공격 횟수 보장
• 3차원 DP 배열을 사용해 각 상태에 도달하는데 필요한 최소 공격 횟수를 저장한다. -> 중복 계산을 피할 수 있음

 

✨ 제출 코드

메모리: 15268 KB

시간: 104 ms

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

public class Main{
    static int[][] possibleAttack = {{9,3,1},{9,1,3},{3,9,1},{3,1,9},{1,9,3},{1,3,9}};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int[] SCV = new int[3];

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

        // 각 상태에 도달하는데 필요한 최소 공격 횟수
        int[][][] dp = new int[SCV[0] + 1][SCV[1] + 1][SCV[2] + 1];
        dp[SCV[0]][SCV[1]][SCV[2]] = 0;
        bfs(SCV, dp);
        System.out.println(dp[0][0][0]);

    }

    private static void bfs(int[] SCV, int[][][]dp){
        Queue<int[]> q = new LinkedList<>();
        q.add(SCV);

        while(!q.isEmpty()){
            int[] tmp = q.poll();

            if(tmp[0] == 0 && tmp[1] == 0 && tmp[2] == 0) break;

            for(int i = 0; i < 6; i++){ // 모든 경우의 공격
                int[] attack = possibleAttack[i];

                int a = Math.max(tmp[0] - attack[0], 0); // 체력이 음수가 될 수 없다.
                int b = Math.max(tmp[1] - attack[1], 0);
                int c = Math.max(tmp[2] - attack[2], 0);

                if(dp[a][b][c] == 0) { // 아직 방문하지 않은 상태라면
                    q.add(new int[]{a, b, c});
                    dp[a][b][c] = dp[tmp[0]][tmp[1]][tmp[2]] + 1;

                }
            }
        }

    }
}