뮤탈리스크

 

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

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

struct SCV
{
	int F, S, T;
};

int attack[6][3]{
	{9,3,1},
	{9,1,3},
	{3,9,1},
	{3,1,9},
	{1,3,9},
	{1,9,3}
};
int n;
int hp[61][61][61];
queue<SCV> scv;
vector<int>temp;

int BFS()
{
	hp[scv.front().F][scv.front().S][scv.front().T] = 1;
	while (scv.empty() == false)
	{
		int f = scv.front().F;
		int s = scv.front().S;
		int t = scv.front().T;
		scv.pop();
		if (f == 0 && s == 0 && t == 0)
			break;
		

		for (int i = 0; i < 6; i++)
		{
			int damageF = max(0 ,f-attack[i][0]);
			int damageS = max(0 ,s-attack[i][1]);
			int damageT = max(0 ,t-attack[i][2]);
			
			if (hp[damageF][damageS][damageT] != 0)
				continue;

			hp[damageF][damageS][damageT] = hp[f][s][t] + 1;
			scv.push({ damageF,damageS,damageT });

		}
	}

	return hp[0][0][0]-1;
}

int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		int a{ };
		cin >> a;
		temp.push_back(a);
	}
	scv.push({ temp[0],temp[1],temp[2] });
	
	cout<<BFS()<<endl;
}

• SCV의 수가 최대 3명이고, 데미지의 경우의 수가 총 6개를 3명한태 나눠야한다
• 그를 위해 attack 이차원 배열을 만들어 경우의 수를 모두 저장해준다
• 또한 3차원 배열을 만들어 각각의 SCV의 체력을 index로 사용하여 그 배열에 index에 들어간 회차(?)를 count하여 모든 SCV의 체력이 0일 때 값을 출력해준다
• 이를 위해 struct 로 SCV의 각각의 체력을 저장해줄 수 있에 해주고 이를 queue에 사용할 곳이다
• 이제 SCV의 체력을 입력받아 queue에 저장해주고 BFS를 돌리면 될것이다
• BFS를 시작하면서 hp 배열에 SCV 체력을 index로 현재 배열에 1을 저장해주고, while문을 돌면서 일반적으로 BFS를 만들어 줄 것이다
• 이때 for문안에서 damage를 계산할 것인데 현재 scv체력과 attack배열에 경우의 수들을 뺀뒤 0과 비교해 큰 수를 damage에 저장해 이를 hp배열에 넣어 0이 아니면 continue를, 그렇지 않으면 hp에 index로 사용해 이전 hp에 1을 더한 값을 저장해주고 queue에 저장해준다
• 이러한 과정을 거치고 함수가 탈출할 때 hp가 모두 0일때를 return해주면 된다