[Java] 백준 12863 뮤탈리스크

뮤탈리스크

분석

• 뮤탈리스크는 한번에 3개의 SCV를 공격함
• 첫번째로 공격하는 SCV는 9의 체력을 소모
• 두번째로 공격하는 SCV는 3의 체력을 소모
• 세번째로 공격하는 SCV는 1의 체력을 소모
• SCV의 체력이 0이하가 되면 파괴
• 공격횟수를 최소로 해서 모든 SCV를 파괴하기

입력

• N : SCV의 수 1 ≤ N ≤ 3
• 각각의 SCV의 체력 <= 60

출력
모든 SCV를 파괴하기 위한 공격 횟수의 최솟값을 출력

---

풀고 싶어서 당당하게 골랐는데 풀이 방법 생각할 때부터 문제 이해를 잘못하고 시작했다... 합쳐서 때릴 수 있는 게 아니라 무조건 [9,3,1]로 하나만 때릴 수 있다는 점

그래서 생각한 게 때릴 수 있는 경우는 무조건
[9,3,1], [9,1,3], [3,9,1], [3,1,9], [1,9,3], [1,3,9] 밖에 없다는 점은 생각을 했는데 이걸 어떻게 활용하지...? 싶었다

추가로 dp로 최소 횟수 갱신하면서 풀어야겠다고도 생각했는데 최소 횟수를 구할 방법이 도저히 생각나지 않아 다른 사람의 풀이를 훔쳐보았다......

참고한 블로그

• 블로그 내의 그림처럼 모든 경우의 수에서 그래프로 나타내보면, 위에 언급한 모든 경우의 수에서 (0,0,0)에 도달하는 최소 횟수를 구할 수 있다
• 레벨별로 탐색하여 최단 거리를 구하는 개념 -> BFS!!

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Baekjoon_12869 {
    static int[][] damage = {
            {9, 3, 1},
            {9, 1, 3},
            {3, 1, 9},
            {3, 9, 1},
            {1, 3, 9},
            {1, 9, 3}
    };

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int N = scanner.nextInt(); // SCV의 수
        int[] scv = new int[3]; // SCV 체력 배열
        boolean[][][] visited = new boolean[61][61][61];
        Queue<int[]> queue = new LinkedList<>();

        for (int i = 0; i < N; i++) {
            scv[i] = scanner.nextInt();
        }

        // N이 3보다 적으면 나머지는 0으로 채우기
        while (N < 3) {
            scv[N++] = 0;
        }

        queue.add(new int[]{scv[0], scv[1], scv[2], 0}); // {체력1, 체력2, 체력3, 공격횟수}
        visited[scv[0]][scv[1]][scv[2]] = true;

        int answer = Integer.MAX_VALUE;

        while (!queue.isEmpty()) {
            int[] current = queue.poll(); // 파이썬의 pop과 같음
            int cur0 = current[0], cur1 = current[1], cur2 = current[2];
            int attackCount = current[3];

            // 모든 SCV의 체력이 0 이하인지 확인
            if (cur0 <= 0 && cur1 <= 0 && cur2 <= 0) {
                answer = Math.min(answer, attackCount);
                continue;
            }

            for (int[] dmg : damage) {
                int next0 = Math.max(0, cur0 - dmg[0]);
                int next1 = Math.max(0, cur1 - dmg[1]);
                int next2 = Math.max(0, cur2 - dmg[2]);

                if (!visited[next0][next1][next2]) {
                    visited[next0][next1][next2] = true;
                    queue.add(new int[]{next0, next1, next2, attackCount + 1});
                }
            }
        }

        System.out.println(answer);
    }
}

• 큐에는 남은 체력 + 공격 횟수가 저장됨
• BFS는 너비 우선 탐색이기 때문에, 가장 먼저 모든 체력이 0이 되는 경우가 최소 횟수임

처음에는 0 이하가 아니라 0으로 했다가 틀리고,,, 어렵다 🥹