[백준] 12869번: 뮤탈리스크 (C++)

12869번: 뮤탈리스크

---

문제)

수빈이는 강호와 함께 스타크래프트 게임을 하고 있다. 수빈이는 뮤탈리스크 1개가 남아있고, 강호는 SCV N개가 남아있다.

각각의 SCV는 남아있는 체력이 주어져있으며, 뮤탈리스크를 공격할 수는 없다. 즉, 이 게임은 수빈이가 이겼다는 것이다.

뮤탈리스크가 공격을 할 때, 한 번에 세 개의 SCV를 공격할 수 있다.

1. 첫 번째로 공격받는 SCV는 체력 9를 잃는다.
2. 두 번째로 공격받는 SCV는 체력 3을 잃는다.
3. 세 번째로 공격받는 SCV는 체력 1을 잃는다.

SCV의 체력이 0 또는 그 이하가 되어버리면, SCV는 그 즉시 파괴된다. 한 번의 공격에서 같은 SCV를 여러 번 공격할 수는 없다.

남아있는 SCV의 체력이 주어졌을 때, 모든 SCV를 파괴하기 위해 공격해야 하는 횟수의 최솟값을 구하는 프로그램을 작성하시오.

 

 

 

입력 :

첫째 줄에 SCV의 수 N (1 ≤ N ≤ 3)이 주어진다. 둘째 줄에는 SCV N개의 체력이 주어진다. 체력은 60보다 작거나 같은 자연수이다.

 

 

 

출력 :

첫째 줄에 모든 SCV를 파괴하기 위한 공격 횟수의 최솟값을 출력한다.

 

 

 

 

 

풀이)

이 문제는 뮤탈리스크의 가능한 모든 공격의 순서를 탐색하면서 "최소 공격 횟수"를 구해야 하는 문제이다.

 

따라서 각 scv의 체력을 visited 배열로 설정한 뒤, 뮤탈리스크 공격을 for문을 통해bfs로 접근하면 최소 공격 횟수를 구할 수 있다.

 

// 일반적인 2차원 그래프 탐색에서 이렇게 썼다면,
int dx[] = { -1, 0, 1, 0 };
int dy[] = { 0, -1, 0, 1 };
 
// 뮤탈리스크의 공격을 다음과 같이 이용한다.
int attack[6][3] =
{
    {9, 3, 1},
    {9, 1, 3},
    {3, 9, 1},
    {3, 1, 9},
    {1, 9, 3},
    {1, 3, 9}
}

 

이 문제에 대한 소스 코드는 다음과 같다.

 

#include <iostream>
#include <queue>
#include <algorithm>
 
using namespace std;
int n;
 
int a[3];
int visited[64][64][64];
 
int attack[6][3] =
{
    {9, 3, 1},
    {9, 1, 3},
    {3, 9, 1},
    {3, 1, 9},
    {1, 9, 3},
    {1, 3, 9}
};
 
// queue를 좀 더 쉽게 다루기 위한 struct
struct A
{
    int a, b, c;
};
 
 
int bfs(int a, int b, int c)
{
    queue<A> q;
    // 현재 체력으로부터 출발
    visited[a][b][c] = 1;
    q.push({ a, b, c });
 
    while (!q.empty())
    {
        int a = q.front().a;
        int b = q.front().b;
        int c = q.front().c;
        q.pop();
 
        // 모든 scv의 체력이 0인 상태에 도달한다면 break;
        if (visited[0][0][0]) break;
 
        for (int i = 0; i < 6; i++)
        {
            // 각 scv의 체력은 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]);
            
            // 이미 방문했던 곳이라면 최단거리가 아니므로 continue
            if (visited[na][nb][nc]) continue;
            visited[na][nb][nc] = visited[a][b][c] + 1;
            q.push({ na, nb, nc });
        }
    }
 
    return visited[0][0][0] - 1;
}
 
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];
    }
 
    // scv의 체력에 대해서 bfs를 실시한다.
    cout << bfs(a[0], a[1], a[2]);
 
    return 0;
}
 

 

---

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

12869번: 뮤탈리스크