백준 12869번 - 뮤탈리스크

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

BFS는 항상 최적을 보장하기 때문에 큐를 이용하여 공격 회수의 최소값을 구하면 된다.

단순 DFS를 이용하게 되면 최소값과 상관없이 모든 경우를 확인하기 때문에 시간초과에 걸리게 된다.

항상 3개의 scv가 있다고 가정하였고, scv의 체력이 오름차순으로 정렬되어 있을 때

다음 순열을 이용하여 총 6개의 조합에서 9,3,1씩 체력을 줄인 후에 큐에 담았다.(음수일 경우 0으로)

scv 3개의 체력이 있을 때, 확인 체크 여부를 하지 않는다면 메모리 초과에 걸리기 때문에

visited를 이용하여 이전에 확인하지 않았을 경우에만 큐에 담아줘야 한다.(오름차순으로 체력을 정렬한 뒤)

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
 
int ans=0;
int attack[3]={9,3,1}; //공격 데미지
int visited[61][61][61]={0}; //[a][b][c] 남아있는 체력 a,b,c일때 확인 여부
 
struct str{
    int scv1;
    int scv2;
    int scv3;
    int cnt;
    str(int scv1,int scv2,int scv3,int cnt):scv1(scv1),scv2(scv2),scv3(scv3),cnt(cnt){};
};
 
int main(){
    
    int N;
    cin>>N;
    
    int scv[3]={0}; //scv의 체력
    for(int i=0;i<N;i++)
        cin>>scv[i];
    
    sort(scv,scv+3); //다음 순열을 위해 정렬
    
    queue<str> q;
    q.push(str(scv[0],scv[1],scv[2],0));
    visited[scv[0]][scv[1]][scv[2]]++;
    
    while(!q.empty()){
        
        scv[0]=q.front().scv1;
        scv[1]=q.front().scv2;
        scv[2]=q.front().scv3;
        int cnt=q.front().cnt;
        q.pop();
        
        if(scv[2]==0){ //오름차순으로 정렬된 것 중에 가장 큰게 0이면
            ans=cnt;
            break;
        }
        
        int temp_scv[3]={0};
        do{
            
            for(int i=0;i<3;i++)
                temp_scv[i]=(scv[i]-attack[i]>0)? scv[i]-attack[i]:0;
            
            sort(temp_scv,temp_scv+3);
            
            if(!visited[temp_scv[0]][temp_scv[1]][temp_scv[2]]){
                visited[temp_scv[0]][temp_scv[1]][temp_scv[2]]++;
                q.push(str(temp_scv[0],temp_scv[1],temp_scv[2],cnt+1));
            }
            
        }while(next_permutation(scv,scv+3)); //다음 순열
        
    }
    
    cout<<ans<<endl;
    return 0;
}