[BOJ/Gold4] 12869번 뮤탈리스크 - JAVA[자바]

난이도 : 골드 4

유형 : BFS / DFS / DP

링크 : https://www.acmicpc.net/problem/12869

구현 시간 : 30분

 

 

 

 

 

문제 풀이

 

이 문제는 BFS / DFS 알고리즘의 유형으로, 뮤탈리스크는 한 번의 공격에서 세 개의 SCV에 각각 9, 3, 1의 피해를 줄 수 있으며, 세 개의 공격 순서를 자유롭게 선택할 수 있습니다.

즉, 모든 가능한 공격 순서를 고려하여 최소 공격 횟수를 찾아야 하는 문제입니다.

 

얼핏 보면 SCV 체력을 내림차순으로 정렬하고, 9 -> 3 -> 1 순서로 공격하면 쉽게 해결할 수 있지 않나? 싶지만

아래 예제를 보면 그리디하게 문제를 해결할 수 없다는 것을 알 수 있습니다.

SCV의 체력이 (12 , 10, 4)일 때

첫번째 공격 -> 1, 3, 2 순서대로 공격을 하면, 남은 체력은 (12-9, 10-1, 4-3) = (3, 9, 1)입니다.
두번째 공격 -> 2, 1, 3 순서대로 공격을 하면, 남은 체력은 (0, 0, 0)입니다.

즉, 공격 순서를 무조건 내림차순으로 정하는 방식으로 풀면 비효율적인 경로를 선택할 수 있습니다.

따라서, 모든 공격 순서를 고려할 수 있는 탐색 알고리즘 (BFS or DFS + DP) 사용이 필요합니다.

 

 

문제 풀이는 2가지 방식으로 풀이했습니다.

• 1. BFS
  • SCV 체력 상태, 공격 횟수)를 Node로 두고, SCV 체력의 모든 가능한 상태를 큐에 삽입하여 탐색하는 방식입니다.
• 2. DFS + DP
  • DFS를 사용하면서 중복되는 상태를 DP 배열로 저장하여 불필요한 탐색을 줄이는 방식입니다.
  • 각 (SCV 체력 상태)에 대해 이미 계산된 최소 공격 횟수를 기록하고, 같은 상태가 다시 등장하면 저장된 값을 활용합니다.

 

1차 시도 - 통과 (BFS)

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 class Node {
        int[] SCV;
        int cnt;

        public Node(int[] SCV, int cnt) {
            this.SCV = SCV.clone();
            this.cnt = cnt;
        }
    }

    static int[] attack = {9, 3, 1};
    static boolean[][][] visited = new boolean[61][61][61];

    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());
        }

        System.out.println(bfs(SCV));
    }

    public static int bfs(int[] SCV) {
        Queue<Node> q = new LinkedList<>();
        q.offer(new Node(SCV, 0));
        visited[SCV[0]][SCV[1]][SCV[2]] = true;

        while (!q.isEmpty()) {
            Node node = q.poll();
            int[] scv = node.SCV;
            int cnt = node.cnt;

            // 모든 SCV 체력이 0 이하인 경우 최소 공격 횟수 반환
            if (scv[0] <= 0 && scv[1] <= 0 && scv[2] <= 0) {
                return cnt;
            }

            // 6가지 공격 패턴 수행
            for (int i = 0; i < 3; i++) {
                for (int j = 0; j < 3; j++) {
                    if (i == j) continue;
                    for (int k = 0; k < 3; k++) {
                        if (i == k || j == k) continue;

                        int[] nextSCV = {
                                Math.max(scv[0] - attack[i], 0),
                                Math.max(scv[1] - attack[j], 0),
                                Math.max(scv[2] - attack[k], 0)
                        };

                        if (!visited[nextSCV[0]][nextSCV[1]][nextSCV[2]]) {
                            visited[nextSCV[0]][nextSCV[1]][nextSCV[2]] = true;
                            q.offer(new Node(nextSCV, cnt + 1));
                        }
                    }
                }
            }
        }
        return -1;
    }
}

 

 

2차 시도 - 통과 (DFS)

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

public class Main {
    static int[][][] dp = new int[61][61][61];
    static int[] attack = {9, 3, 1};

    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());
        }

        // DP 테이블 초기화
        for (int[][] arr2 : dp) {
            for (int[] arr : arr2) {
                Arrays.fill(arr, -1);
            }
        }
        System.out.println(dfs(SCV[0], SCV[1], SCV[2]));
    }

    public static int dfs(int a, int b, int c) {
        if (a <= 0 && b <= 0 && c <= 0) return 0;
        
        a = Math.max(a, 0);
        b = Math.max(b, 0);
        c = Math.max(c, 0);

        // 이미 방문한 경우
        if (dp[a][b][c] != -1) return dp[a][b][c];

        int minValue = Integer.MAX_VALUE;

        // 6가지 공격 조합 수행
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                if (i == j) continue;
                for (int k = 0; k < 3; k++) {
                    if (i == k || j == k) continue;
                    
                    int dfs = dfs(a - attack[i], b - attack[j], c - attack[k]);
                    minValue = Math.min(minValue, dfs);
                }
            }
        }
        // 최소 공격 횟수 반환
        return dp[a][b][c] = minValue + 1;
    }
}