백준 12869 - 뮤탈리스크(C++)

문제 링크입니다. https://www.acmicpc.net/problem/12869

12869번: 뮤탈리스크

Dp로 풀 수 있지만, BFS로 푸는게 더 간단해 보여 약간의 노다가를 추가한 BFS로 풀었습니다.

3개의 SCV가 각각 9 or 3 or 1의 값이 빼집니다.

따라서 모든 경우를 확인한 뒤, 전부 0이 된 최소 횟수를 출력해주면 됐습니다.

 

 

자세한 것은 코드를 참고해주세요

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>

using namespace std;

int N;
int hp[3];
int check[61][61][61];
typedef struct M{
    int hp[3], cost;
}M;

int nine(int x){
    return x-9 > 0 ? x-9 : 0;
}

int three(int x){
    return x-3 > 0 ? x-3 : 0;
}

int one(int x){
    return x-1 > 0 ? x-1 : 0;
}

int bfs(){
    queue<M> q;
    M input;
    input.cost = 0;
    for(int i = 0; i < 3; i++) input.hp[i] = hp[i];
    q.push(input);
    check[hp[0]][hp[1]][hp[2]] = 1;
    while(!q.empty()){
        int x = q.front().hp[0];
        int y = q.front().hp[1];
        int z = q.front().hp[2];
        int cost = q.front().cost;
        q.pop();
        if(x <= 0 && y <= 0 && z <= 0) return cost;
        if(check[nine(x)][three(y)][one(z)] == 0) {
            q.push({{nine(x), three(y), one(z)}, cost + 1});
            check[nine(x)][three(y)][one(z)] = 1;
        }
        if(check[nine(x)][one(y)][three(z)] == 0) {
            q.push({{nine(x), one(y), three(z)}, cost + 1});
            check[nine(x)][one(y)][three(z)] = 1;
        }
        if(check[three(x)][nine(y)][one(z)] == 0) {
            q.push({{three(x), nine(y), one(z)}, cost + 1});
            check[three(x)][nine(y)][one(z)] = 1;
        }
        if(check[three(x)][one(y)][nine(z)] == 0){ 
            q.push({{three(x), one(y), nine(z)}, cost + 1});
            check[three(x)][one(y)][nine(z)] = 1;
        }
        if(check[one(x)][nine(y)][three(z)] == 0){
            q.push({{one(x), nine(y), three(z)}, cost + 1});
            check[one(x)][nine(y)][three(z)] = 1;
        }
        if(check[one(x)][three(y)][nine(z)] == 0){
            q.push({{one(x), three(y), nine(z)}, cost + 1});
            check[one(x)][three(y)][nine(z)]  = 1;
        } 
    }
}

void solve(){
    cout << bfs();
}

int main(){
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    for(int i = 0; i < N; i++) cin >> hp[i];
    solve();
    return 0;
}

 

 

질문 및 조언은 댓글을 남겨주세요