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

1. 문제

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

12869번: 뮤탈리스크

 

 

2. 풀이과정

방법 1. BFS

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

public class Main {

    static int damage[][] = new int[][]{
            {9, 3, 1}, {9, 1, 3},
            {3, 9, 1}, {3, 1, 9},
            {1, 3, 9}, {1, 9, 3}
    };
    static boolean dp[][][];

    public static int attack(int[] scv){
        int result = 0;
        Queue<int[]> q = new LinkedList<>();//a, b, c
        q.add(new int[]{scv[0], scv[1], scv[2]});
        outloop : while(true){
            result ++;
            for(int i=0, size=q.size(); i<size; i++){
                int[] now = q.poll();
                for(int a=0; a<6; a++){
                    int n1 = Math.max(0, now[0]-damage[a][0]);
                    int n2 = Math.max(0, now[1]-damage[a][1]);
                    int n3 = Math.max(0, now[2]-damage[a][2]);
                    if(!dp[n1][n2][n3]){
                        if(n1==0 && n2==0 &&n3==0){
                            break outloop;
                        }
                        dp[n1][n2][n3] = true;
                        q.add(new int[]{n1, n2, n3});
                    }
                }
            }
        }
        return result;
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int scv[] = new int[3];
        dp = new boolean[61][61][61];

        for(int i=0; i<N; i++){
            scv[i] = Integer.parseInt(st.nextToken());
        }

        System.out.println(attack(scv));

    }
}

 

결과

 

 

방법 2. DFS

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

public class Main {

    static int dp[][][];
    public static int attack(int a, int b, int c){
        a = Math.max(0, a);
        b = Math.max(0, b);
        c = Math.max(0, c);
        if(a==0 && b==0 && c==0){return 0;}
        if(dp[a][b][c]!=0){return dp[a][b][c];}

        int min = 999_999_999;
        min = Math.min(min, attack(a-9, b-3, c-1));
        min = Math.min(min, attack(a-9, b-1, c-3));
        min = Math.min(min, attack(a-1, b-3, c-9));
        min = Math.min(min, attack(a-1, b-9, c-3));
        min = Math.min(min, attack(a-3, b-1, c-9));
        min = Math.min(min, attack(a-3, b-9, c-1));
        dp[a][b][c] = min+1;
        return dp[a][b][c];
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int scv[] = new int[3];
        dp = new int[61][61][61];

        for(int i=0; i<N; i++){
            scv[i] = Integer.parseInt(st.nextToken());
        }

        System.out.println(attack(scv[0], scv[1], scv[2]));

    }
}

 

결과