12869_뮤탈리스크

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

12869번: 뮤탈리스크

접근

- 순열 생성을 통해 SCV의 공격 순서를 정한다

- n이 3가지 제한되어 있으므로 3! = 6 이다

- typedef vector<int> scv 로 scv의 상태를 정한다

- 공격횟수를 저장하기 위헤 map<scv, int> 를 사용한다

- 만약 hp가 0이상인 scv가 하나도 없다면 탐색을 멈추고 도달 하기 까지의 거리를 반환한다

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <map>

using namespace std;

typedef vector<int> scv;
map<scv, int> dist;
int n;

int bfs(scv start){
    queue<scv> q;
    q.push(start);
    dist[start] = 0;
    vector<int> indexes;
    
    for(int i = 0 ; i < n ; i++){
        indexes.push_back(i);
    }
    
    while(!q.empty()){
        scv current = q.front();
        q.pop();
        int sum = 0;
        for(int i = 0 ; i < current.size() ; i++){
            int hp = current[i];
            if(hp > 0) sum += hp;
            
        }
        if(sum == 0){
            return dist[current];
        }
        scv next;
        do{
            int kill = 9;
            next = current;
            
            for(int idx : indexes){
                //cout<<kill<<" ";
                next[idx]-=kill;
                kill /= 3;
                
            }
            
            if(dist.count(next) > 0 ) continue;
            dist[next] = dist[current]+1;
            q.push(next);
        }while(next_permutation(indexes.begin(), indexes.end()));
        
    }
    
    return -1;
}

int main(int argc, const char * argv[]) {
    scanf("%d", &n);
    scv start = scv(n, 0);
    for(int i = 0 ; i < n ; i++){
        scanf("%d", &start[i]);
    }
    
    cout<<bfs(start)<<endl;
    
    return 0;
}