[c++] 백준 12869, 뮤탈리스크

백준 12869

🌲 문제 요약

남아있는 SCV의 체력이 주어졌을 때, 뮤탈리스크가 모든 SCV를 파괴하기 위해 공격해야 하는 횟수의 최솟값을 구하는 문제.

🌲 문제 풀이

BFS를 이용하여 문제를 해결한다.
함수 go는 배열 _a에 담긴 뮤탈리스크의 데미지 정보를 통해 SCV의 체력을 줄여 나가며 그때그때의 정보를 배열 visited에 저장한다. visited[0][0][0]의 값이 0이 아니라면, 모든 SCV의 체력이 0이 되었다는 뜻이므로 visited[0][0][0] - 1을 return하고 함수를 종료한다.

🌲 주의

큐 q가 한 번의 push마다 세 개의 값을 저장해야 하므로, struct A를 따로 선언하여 q의 사용이 좀 더 용이해지도록 한다.

🌲 코드

#include <bits/stdc++.h>

using namespace std;
int n, a[3], visited[65][65][65];
int _a[6][3] = {
	{9, 3, 1},
	{9, 1, 3},
	{3, 9, 1},
	{3, 1, 9},
	{1, 9, 3},
	{1, 3, 9}
};
struct A {
	int a, b, c;
};
queue<A> q;

int go(int x, int y, int z) {
	visited[x][y][z] = 1;
	q.push({x, y, z});
	while (q.size()) {
		x = q.front().a;
		y = q.front().b;
		z = q.front().c;
		q.pop();
		if (visited[0][0][0]) break;
		for (int i = 0; i < 6; i++) {
			int nx = max(0, x - _a[i][0]);
			int ny = max(0, y - _a[i][1]);
			int nz = max(0, z - _a[i][2]);
			if (visited[nx][ny][nz]) continue;
			visited[nx][ny][nz] = visited[x][y][z] + 1;
			q.push({nx, ny, nz});
		}
	}
	return visited[0][0][0] - 1;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	cout << go(a[0], a[1], a[2]) << '\n';
	
	return 0;
}