코드카타 문제
오늘의 코드카타 문제는 백준에 있었던 문제인 12869번 뮤탈리스크다.
문제를 요약하자면, 뮤탈리스크 1마리가 SCV N개(최대 3개)를 전부 파괴하는 데 필요한 최소 공격 횟수를 구하는 것이었다.
한 번 공격하면 서로 다른 세 SCV에게 각각 9, 3, 1의 피해를 준다. 이때 9/3/1을 어느 SCV에 꽂을지는 마음대로 정할 수 있고, 체력이 0 이하가 된 SCV는 즉시 파괴된다. 즉 "매 공격마다 9/3/1을 어떻게 분배해야 모든 SCV를 가장 빨리 0 이하로 만드는가"를 찾는 문제다.
문제를 보자마자 제약 조건부터 확인했다.
- SCV는 최대 3개, 각 체력은 최대 60.
여기서 핵심은 세 가지였다.
- 상태가
(hp1, hp2, hp3)로 완전히 결정된다. 각 체력이 0~60이라, 가능한 상태는 최악이라도61³가지뿐이다. - 한 공격에서 9/3/1을 세 SCV에 배정하는 방법은
3! = 6가지다. 데미지 값은 고정이고 "누구에게 줄지"만 고르면 되니, 순열 6개를 미리 만들어 두면 된다. - 모든 공격의 비용이 1로 같다. 즉 가중치 없는 그래프에서 시작 상태 →
(0,0,0)까지의 최단 거리를 구하는 문제이고, BFS로 푸는 것이 적합하다고 생각했다.
상태 공간이 작고 모든 간선의 비용이 동일하니, 굳이 그리디 같은 휴리스틱을 고민할 필요 없이 BFS로 상태를 전부 훑는 완전 탐색으로 충분하다고 판단했다.
그래서 풀이를 세 부분으로 나눴다.
- 상태 정의: 세 SCV의 체력을 하나의 상태로 묶는다.
- 전이: 한 상태에서 6가지 데미지 분배로 다음 상태들을 만든다.
- BFS: 시작 상태에서
(0,0,0)까지의 최단 레벨을 구한다.
1. 상태 정의
SCV 세 개의 체력을 묶어 하나의 상태로 본다. Data 구조체에 hp[3]을 담고, 입력으로 받은 N개의 체력을 앞에서부터 채운다.
struct Data {
int hp[3];
Data() { hp[0] = hp[1] = hp[2] = 0; }
Data(int a1, int a2 = 0, int a3 = 0) { hp[0]=a1; hp[1]=a2; hp[2]=a3; }
};N이 3보다 작아도 따로 분기할 필요가 없다. Data를 0으로 초기화해 두면, 존재하지 않는 SCV는 체력이 0 → 처음부터 "파괴됨" 상태이므로 답에 전혀 영향을 주지 않는다. 그래서 N=1, 2, 3을 같은 코드로 처리한다.
방문 체크는 3차원 배열 arr[61][61][61]로 했다.
2. 전이
매 공격은 9/3/1을 세 SCV에 나눠 주는 것이므로, 가능한 분배는 다음 6가지다.
int damage[6][3] = {
{ 9, 3, 1 }, { 9, 1, 3 }, { 3, 9, 1 },
{ 3, 1, 9 }, { 1, 9, 3 }, { 1, 3, 9 }
};한 상태에서 이 6가지를 각각 적용하면 6개의 다음 상태가 나온다.
int d1 = max(0, d.hp[0] - damage[i][0]);체력이 음수로 내려가는 건 의미가 없다. -5든 0이든 똑같이 "파괴됨"이므로, max(0, ...)로 잘라 줘야 두 상태가 하나로 합쳐진다. 이 클램핑이 없으면 상태가 음수 범위로 퍼져 배열 인덱싱이 깨지고 방문해야 할 상태도 폭증한다.
3. BFS로 최단 횟수
시작 상태를 큐에 넣고, 뽑을 때마다 6가지 전이를 만들어 아직 방문하지 않은 상태만 큐에 넣는다. 모든 간선의 비용이 1이라 BFS의 레벨이 곧 공격 횟수이고, (0,0,0)을 처음 꺼내는 순간의 레벨이 최소 횟수가 된다.
방문 표시는 큐에 넣는 시점에 한다. 같은 상태가 큐에 여러 번 쌓이는 걸 막아 불필요한 탐색을 줄이기 위해서다.
코드
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;
int n;
// 한 번의 공격에서 9/3/1을 세 SCV에 배정하는 6가지 순열
int damage[6][3] = {
{ 9, 3, 1 }, { 9, 1, 3 }, { 3, 9, 1 },
{ 3, 1, 9 }, { 1, 9, 3 }, { 1, 3, 9 }
};
int arr[61][61][61]; // 방문 체크 (각 SCV 체력 0~60)
// 세 SCV의 체력을 묶은 상태
struct Data
{
int hp[3];
Data() { hp[0] = 0; hp[1] = 0; hp[2] = 0; }
Data(int a1, int a2 = 0, int a3 = 0)
{
hp[0] = a1; hp[1] = a2; hp[2] = a3;
}
};
void bfs(Data data)
{
queue<pair<Data, int>> q; // { 상태, 공격 횟수 }
q.push({ data, 0 });
arr[data.hp[0]][data.hp[1]][data.hp[2]] = 1;
while (!q.empty())
{
Data d = q.front().first;
int val = q.front().second;
q.pop();
// 모든 SCV 파괴 → 현재 레벨이 최소 공격 횟수
if (d.hp[0] == 0 && d.hp[1] == 0 && d.hp[2] == 0)
{
cout << val << "\n";
return;
}
// 6가지 데미지 분배를 각각 적용
for (int i = 0; i < 6; ++i)
{
int d1 = max(0, d.hp[0] - damage[i][0]); // 음수 체력은 0으로 클램핑
int d2 = max(0, d.hp[1] - damage[i][1]);
int d3 = max(0, d.hp[2] - damage[i][2]);
if (arr[d1][d2][d3] == 0)
{
arr[d1][d2][d3] = 1; // 큐에 넣는 시점에 방문 표시
q.push({ Data(d1, d2, d3), val + 1 });
}
}
}
}
int main()
{
cin >> n;
Data data{}; // 0으로 초기화 → 없는 SCV는 처음부터 파괴됨
for (int i = 0; i < n; ++i)
{
int a;
cin >> a;
data.hp[i] = a;
}
bfs(data);
return 0;
}