백준 12869 //visit[체력][체력][체력]=최단거리(공격횟수) /visit idx를 체력으로 사용하라.

12869번: 뮤탈리스크 (acmicpc.net)

12869번: 뮤탈리스크

/*
* bfs algorithm
* 1.초기화
* 2.종료조건
* 3.next
* 4.next 방문체크
* 5.visit[next] 갱신
*/

 

*핵심로직

1. visit[체력][체력][체력] = 최단거리(공격횟수)

1.1 idx에 각각 체력저장.

2.v[0][0][0] 에 방문했다? -> bfs이므로 ->

   최초 체력 0,0,0으로 만든애가 최단거리임. -> 출력. 끝.

 

#include <bits/stdc++.h> 
using namespace std;
int a[3];
int n, dx[4] = { -1,0,1,0 }, dy[4] = { 0,-1,0,1 };
int visited[64][64][64];
vector<pair<int, int>> v;
int mutal[6][3] = {
	{9,3,1},
	{9,1,3},
	{3,1,9},
	{3,9,1},
	{1,3,9},
	{1,9,3}
};

bool in(int a, int b) {
	return 0 <= a && a < n && 0 <= b && b < n;
}
/*
* tuple<int,int,int>보다
* struct로 삼변수저장.
* class는 push(1,2,3)이 안됨.
*/
struct A {
	int a, b, c;
};
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	cin >> n ;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	
	/*
	* bfs algorithm
	* 1.초기화
	* 2.종료조건
	* 3.next
	* 4.next 방문체크
	* 5.visit[next] 갱신
	*/
	queue<A> q;
	q.push({ a[0],a[1],a[2] });
	visited[a[0]][a[1]][a[2]] = 1;
	while (q.size())
	{
		int a = q.front().a;
		int b = q.front().b;
		int c = q.front().c;
		q.pop();

		if (visited[0][0][0]) break;
		for (int i = 0; i < 6; ++i)
		{
			int na = max(0, a - mutal[i][0]);
			int nb = max(0, b - mutal[i][1]);
			int nc = max(0, c - mutal[i][2]);
			if (visited[na][nb][nc]) continue;
			visited[na][nb][nc] = visited[a][b][c] + 1;
			q.push({ na,nb,nc });
		}
	}

	cout << visited[0][0][0]-1;
}


	
/*
3
12 10 4
2 */