[백준] 12869번 - 뮤탈리스크 [Java]

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

 

[백준] 12869번 - 뮤탈리스크 [Java]

[백준] 12869번 - 뮤탈리스크 [Java]

---

1.  아이디어

 

BFS, DFS, 다이나믹 프로그래밍 3가지 방법을 활용해서 해결했다.

---

2. 문제풀이

 

SCV는 몇 개가 주어지든 3개로 맞춰서 배열에 담았다. 3개 미만으로 주어지면 체력 0의 유령 SCV라고 가정했다. 이는 이후 풀이에서 SCV가 파괴된 경우도 동일하다. 뮤탈리스크의 공격은 9-3-1로 들어오는데 이 공격이 SCV에게 들어오는 것은 순열로 6가지 경우가 있고 각 SCV 상태에 대해 6가지 공격 조합이 추가된다는 흐름으로 구현했다. 공통적으로 현재 상태와 조합을 통해 다음 체력 상태를 반환하는 hit 메서드와 공격 조합에 대한 탐색배열을 작성했고 SCV 체력이 음수가 되지 않게 하여 방문 체크를 진행했다. SCV의 체력은 정렬을 통해 항상 오름차순이 되게 했다.

BFS의 경우 최단거리를 구하면 바로 정답이 되고 DFS는 재귀 깊이를 depth 파라미터로 들고 다니며 SCV의 체력이 모두 0이 되면 출력할 답과 depth를 비교해 최솟값을 저장하도록 했다. 다이나믹 프로그래밍은 탑 타운으로 진행하며 dp 배열에는 현재 체력 조합에 대한 최솟값을 저장하도록 했다. 점화식은 현재 체력 조합일 때 최솟값 = 현재 체력 조합일 때 최솟값과 공격 후 체력 조합 + 1(공격 1회) 중 최솟값이다.

종료 조건은 모든 SCV가 파괴된 상태면 0을 반환하고 현재 체력 조합일 때 공격 횟수가 저장된 적이 있으면 해당 값을 바로 반환하도록 했다.

---

3. 코드

 

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

public class Main_BFS {

    // 공격 조합에 대한 탐색 배열
    private static final int[] d1 = {1, 1, 3, 3, 9, 9};
    private static final int[] d2 = {3, 9, 1, 9, 1, 3};
    private static final int[] d3 = {9, 3, 9, 1, 3, 1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

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

        int dist = bfs(arr);
        System.out.println(dist);
    }

    // SCV 체력을 담은 배열을 받아서 공격 후 변경된 체력을 배열로 반환
    private static int[] hit(int[] arr, int d1, int d2, int d3) {
        int[] tmp = arr.clone();
        tmp[0] = Math.max(tmp[0] - d1, 0);
        tmp[1] = Math.max(tmp[1] - d2, 0);
        tmp[2] = Math.max(tmp[2] - d3, 0);
        Arrays.sort(tmp);
        return tmp;
    }

    private static int bfs(int[] start) {
        Queue<int[]> q = new ArrayDeque<>();
        q.offer(start);

        boolean[][][] visited = new boolean[1 + 60][1 + 60][1 + 60];
        visited[start[0]][start[1]][start[2]] = true;

        int dist = 0;

        while (!q.isEmpty()) {
            int len = q.size();

            for (int i = 0; i < len; i++) {
                int[] node = q.poll();
                if (node[2] == 0) return dist;

                for (int dir = 0; dir < 6; dir++) {
                    int[] next = hit(node, d1[dir], d2[dir], d3[dir]);

                    if (visited[next[0]][next[1]][next[2]]) continue;

                    q.offer(next);
                    visited[next[0]][next[1]][next[2]] = true;
                }
            }

            dist++;
        }

        return -1;
    }

}

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

public class Main_DFS {

    // 공격 조합에 대한 탐색 배열
    private static final int[] d1 = {1, 1, 3, 3, 9, 9};
    private static final int[] d2 = {3, 9, 1, 9, 1, 3};
    private static final int[] d3 = {9, 3, 9, 1, 3, 1};

    private static final boolean[][][] visited = new boolean[1 + 60][1 + 60][1 + 60];
    private static int ans = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

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

        dfs(arr, 0);

        System.out.println(ans);
    }

    // SCV 체력을 담은 배열을 받아서 공격 후 변경된 체력을 배열로 반환
    private static int[] hit(int[] arr, int d1, int d2, int d3) {
        int[] tmp = arr.clone();
        tmp[0] = Math.max(tmp[0] - d1, 0);
        tmp[1] = Math.max(tmp[1] - d2, 0);
        tmp[2] = Math.max(tmp[2] - d3, 0);
        Arrays.sort(tmp);
        return tmp;
    }

    private static void dfs(int[] node, int depth) {
        if (node[2] == 0) {
            ans = Math.min(ans, depth);
            return;
        }

        if (visited[node[0]][node[1]][node[2]]) return;
        visited[node[0]][node[1]][node[2]] = true;

        for (int dir = 0; dir < 6; dir++) {
            int[] next = hit(node, d1[dir], d2[dir], d3[dir]);

            dfs(next, depth + 1);
        }
    }

}

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

public class Main_DP {

    // 공격 조합에 대한 탐색 배열
    private static final int[] d1 = {1, 1, 3, 3, 9, 9};
    private static final int[] d2 = {3, 9, 1, 9, 1, 3};
    private static final int[] d3 = {9, 3, 9, 1, 3, 1};

    private static final int[][][] dp = new int[1 + 60][1 + 60][1 + 60];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());

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

        for (int i = 0; i <= 60; i++) {
            for (int j = 0; j <= 60; j++) {
                for (int k = 0; k <= 60; k++) {
                    dp[i][j][k] = Integer.MAX_VALUE;
                }
            }
        }

        recur(arr);

        System.out.println(dp[arr[0]][arr[1]][arr[2]]);
    }

    // SCV 체력을 담은 배열을 받아서 공격 후 변경된 체력을 배열로 반환
    private static int[] hit(int[] arr, int d1, int d2, int d3) {
        int[] tmp = arr.clone();
        tmp[0] = Math.max(tmp[0] - d1, 0);
        tmp[1] = Math.max(tmp[1] - d2, 0);
        tmp[2] = Math.max(tmp[2] - d3, 0);
        Arrays.sort(tmp);
        return tmp;
    }

    private static int recur(int[] node) {
        if (node[2] == 0) return 0;
        if (dp[node[0]][node[1]][node[2]] != Integer.MAX_VALUE) return dp[node[0]][node[1]][node[2]];

        for (int dir = 0; dir < 6; dir++) {
            int[] next = hit(node, d1[dir], d2[dir], d3[dir]);

            dp[node[0]][node[1]][node[2]] = Math.min(dp[node[0]][node[1]][node[2]], recur(next) + 1);
        }

        return dp[node[0]][node[1]][node[2]];
    }

}

---

4. 후기

 

- BFS

- DFS

- 다이나믹 프로그래밍