이번에는 백준 12869번 뮤탈리스크 문제를 풀어보았습니다.
처음에는 DFS를 이용하여 모든 공격 경우를 탐색하려고 하였지만, 공격 횟수의 최솟값을 구해야 한다는 점에서 최단 거리 문제와 비슷하다고 생각했습니다.
SCV의 체력을 상태로 두고 BFS를 수행하면 가장 먼저 모든 SCV의 체력이 0이 되는 순간이 정답이 된다고 생각하여 BFS로 구현하였습니다.
문제 설명
뮤탈리스크는 한 번 공격할 때 SCV 세 개를 각각 9, 3, 1의 데미지로 공격할 수 있습니다.
공격 순서는 자유롭게 정할 수 있으며, SCV의 체력이 0 이하가 되면 파괴됩니다.
모든 SCV를 파괴하기 위해 필요한 공격 횟수의 최솟값을 구하는 문제입니다.
풀이 아이디어
SCV의 체력이 (a, b, c) 상태라고 할 때, 한 번 공격하면 새로운 체력 상태로 이동하게 됩니다.
예를 들어 (12, 10, 4)에서 공격을 하면 (3, 7, 3)과 같은 새로운 상태가 만들어집니다.
이처럼 체력을 하나의 상태라고 생각하면 (0, 0, 0)까지 도달하는 최단 횟수를 구하는 문제로 볼 수 있습니다.
따라서 현재 SCV들의 체력을 상태로 두고 BFS를 수행하였습니다.
visited[a][b][c]에는 해당 체력 상태에 도달하기까지의 공격 횟수를 저장하였습니다.
BFS 특성상 가장 먼저 (0, 0, 0)에 도달한 경우가 최단 공격 횟수가 됩니다.
코드
#include <bits/stdc++.h>
using namespace std;
int n;
int min_val = INT_MAX;
int health[3];
int attack[6][3] = {
{9,3,1},
{9,1,3},
{3,9,1},
{3,1,9},
{1,3,9},
{1,9,3}
};
int visited[64][64][64];
struct st{
int a,b,c;
};
queue<struct st> q;
int bfs(int a, int b, int c) {
visited[a][b][c] = 1;
q.push({a,b,c});
while(!q.empty()) {
struct st temp = q.front();
int a = temp.a;
int b = temp.b;
int c = temp.c;
q.pop();
if (visited[0][0][0]) continue;
for (int i = 0; i < 6; i++) {
int na = max(0, a - attack[i][0]);
int nb = max(0, b - attack[i][1]);
int nc = max(0, c - attack[i][2]);
if (visited[na][nb][nc]) continue;
q.push({na,nb,nc});
visited[na][nb][nc] = visited[a][b][c] + 1;
}
}
return visited[0][0][0] - 1;
}
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> health[i];
}
cout << bfs(health[0], health[1], health[2]);
return 0;
}풀이 흐름
- 입력을 받아 SCV들의 체력을 저장합니다.
- 현재 체력 상태
(a, b, c)를 하나의 정점으로 생각합니다. - BFS를 수행하면서 가능한 모든 공격 경우를 탐색합니다.
- 공격 후 감소한 체력을 새로운 상태로 큐에 넣습니다.
- visited 배열에 해당 상태까지 도달하는 공격 횟수를 저장합니다.
(0, 0, 0)상태가 방문되면 최단 공격 횟수가 구해집니다.- 결과를 출력합니다.
구현 포인트
1. 공격 가능한 모든 경우 저장
뮤탈리스크는 9, 3, 1의 공격을 서로 다른 SCV에게 가할 수 있습니다.
따라서 가능한 모든 순열을 미리 저장해두었습니다.
int attack[6][3] = {
{9,3,1},
{9,1,3},
{3,9,1},
{3,1,9},
{1,3,9},
{1,9,3}
};BFS에서는 이 6가지 경우를 모두 탐색하였습니다.
2. 체력 상태를 visited 배열에 저장
현재 SCV들의 체력을 상태로 생각하였습니다.
int visited[64][64][64];예를 들어
visited[10][5][3]은 체력이 (10, 5, 3)인 상태에 도달했는지를 의미합니다.
또한 방문 횟수가 아니라 해당 상태까지 도달하는 공격 횟수를 저장하였습니다.
3. 체력이 음수가 되지 않도록 처리
공격 후 체력이 0보다 작아질 수 있기 때문에 0으로 고정하였습니다.
int na = max(0, a - attack[i][0]);
int nb = max(0, b - attack[i][1]);
int nc = max(0, c - attack[i][2]);이미 파괴된 SCV는 계속 0 상태를 유지하도록 처리하였습니다.
4. BFS를 이용한 최단 공격 횟수 계산
현재 상태에서 공격 가능한 모든 상태를 큐에 넣었습니다.
q.push({na,nb,nc});
visited[na][nb][nc] = visited[a][b][c] + 1;이전 상태의 공격 횟수에 1을 더하여 저장하였습니다.
5. (0, 0, 0) 상태가 정답
모든 SCV가 파괴된 상태는 (0, 0, 0)입니다.
return visited[0][0][0] - 1;visited를 1부터 시작하였기 때문에 마지막에 1을 빼서 정답을 출력하였습니다.
