백준 12869번 뮤탈리스크 풀이(c++)

문제 링크

성능 요약

메모리: 3044 KB, 시간: 0 ms

분류

너비 우선 탐색, 다이나믹 프로그래밍, 그래프 이론, 그래프 탐색

제출 일자

2025년 2월 26일 15:31:30

문제 설명

수빈이는 강호와 함께 스타크래프트 게임을 하고 있다. 수빈이는 뮤탈리스크 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를 파괴하기 위한 공격 횟수의 최솟값을 출력한다.

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int N;

int line[6][3] =
{ {9, 3, 1},
{9, 1, 3},
{3, 9, 1},
{3, 1, 9},
{1, 9, 3},
{1, 3, 9} };
struct tagPosition
{
    int a;
    int b;
    int c;
};
int Visited[61][61][61] = { 0, };

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

    cin >> N;
    vector<int> vSCV(3, 0);

    for (int i = 0; i < N; ++i)
    {
        cin >> vSCV[i];
    }

    tagPosition input = { vSCV[0], vSCV[1], vSCV[2] };
    queue<tagPosition> q;
    q.push(input);

    Visited[q.front().a][q.front().b][q.front().c] = 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 = max(0, a - line[i][0]);
            int nb = max(0, b - line[i][1]);
            int nc = max(0, c - line[i][2]);
            if (Visited[na][nb][nc])
                continue;
            Visited[na][nb][nc] = Visited[a][b][c] + 1;

            q.push({ na, nb, nc });
        }
    }

    cout << Visited[0][0][0] - 1;


    return 0;
}

BFS 를 이용하여 풀이. 입력되는 수가 최대 60인것을 감안하여 입력되는 수를 인덱스로 활용해 풀이하였다.