백준 12869번 - 뮤탈리스크

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

12869번: 뮤탈리스크

 

문제

 SCV가 1 ~ 3대가 있을 때, 뮤탈 리스크가 최소 몇 번을 해야 모든 SCV를 파괴할 수 있는지를 구하는 문제다. 뮤탈리스크가 한번 공격하면 9, 3, 1의 데미지가 각 SCV에게 무작위로 들어간다.

 

풀이 과정

 완전 탐색을 이용했다. 공격할 때 9, 3, 1의 데미지가 랜덤하게 오기 때문에 모든 경우의 수 배열로 만들었다. 이 배열을 이용해서 다음 노드를 탐색하게 된다. 이때 배열의 인덱스가 음수가 되면 안되므로 음수일 경우 0으로 처리해준다. visited에 인덱스는 '[A SCV체력][B SCV 체력][C SCV체력]' 를 의미하게 된다. 해당 체력인 경우의 수에 왔었는지 체크하고 이전 visited에  1을 더해줌으로서 최단 거리를 구한다. 최종적으로 visited[0][0][0]에 도착하게 되면 모든 SCV가 파괴된 것으로 while문을 break로 탈출한다. 출력할 때는 처음 visited가 1부터 시작했으므로 1을 빼고 출력한다.

 SCV가 3대가 아닐 경우를 위해 어떻게 처리해야할지 고민해보았다. SCV 3대를 0으로 초기화되어 있다면 문제 없다는 것을 알았다. SCV의 값이 별도로 입력되지 않으면, 0인 값을 가지고 이미 파괴된 상태이기 때문에 최종 해에 영향을 미치지 않는다.

느낀 점

 처음 풀 때는 단순히 체력이 큰 SCV를 우선으로 타겟하는 식으로 문제를 풀었다. 하지만 모든 경우 최적의 해를 구할 수 없었던 기억이 있다. 이후 문제 푼지가 꽤 되어서 기억이 아에 나지 않았는데, 천천히 생각하다 보니 BFS를 이용한 완전 탐색이 떠올랐고, visited 배열을 이용해 인덱스를 기록하는 방법이 떠올랐다. 조금은 체화된 것 같아서 기뻤다. BFS와 DFS를 이용한 완전 탐색만 자유자제로 적용할 수 있어도 꽤 많은 문제를 풀 수 있을 것 같다. 앞으로도 복습을 꾸준히 해가도록 하자.

 

#include<bits/stdc++.h>
using namespace std;

//공격하는 모든 경우의 수
int atk[6][3] = {
	{9, 3, 1},
	{9, 1, 3},
	{3, 9, 1},
	{3, 1, 9},
	{1, 9, 3},
	{1, 3, 9}
};
//SCV 체력 데이터 입력을 위한 구조체
struct scvs {
	int a, b, c;
};
//방문 처리를 위한 배열
int visited[64][64][64];

//3개 이하의 scv가 입력되었을 때도 0으로 초기화되어 있으므로 무관
int n, scv[3];
queue<scvs> q;

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	//입력
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> scv[i];
	}

	//BFS
	q.push({ scv[0], scv[1], scv[2] });
	visited[scv[0]][scv[1]][scv[2]] = 1; //이때 1부터 시작했기 때문에 출력 때 1을 빼준다.
	while (q.size()){
		int a = q.front().a;
		int b = q.front().b;
		int c = q.front().c;
		q.pop();
		//다음 공격 경우의 수 탐색
		for (int i = 0; i < 6; i++) {
			int na = a - atk[i][0];
			int nb = b - atk[i][1];
			int nc = c - atk[i][2];
			//배열 인덱스가 음수가 되면 안되므로 0 처리
			if (na < 0) na = 0;
			if (nb < 0) nb = 0;
			if (nc < 0) nc = 0;
			if (visited[na][nb][nc]) continue;
			//최단 거리를 구하기 위한 이전 visited + 1
			visited[na][nb][nc] = visited[a][b][c] + 1;
			q.push({ na, nb, nc });
		}
		//모든 SCV가 파괴되었다면 탈출
		if (visited[0][0][0]) break;
	}

	//출력
	cout << visited[0][0][0] - 1;

	return 0;
}