[Baekjoon/C++] 12869번 - 뮤탈리스크

[백준] Baekjoon Online Judge

문제로 이동

 

문제

수빈이는 강호와 함께 스타크래프트 게임을 하고 있다. 수빈이는 뮤탈리스크 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 <queue>
using namespace std;

int num[3];
int arr[61][61][61];

int da[6] = { -9, -9, -3, -1, -3, -1 };
int db[6] = { -3, -1, -9, -9, -1, -3 };
int dc[6] = { -1, -3, -1, -3, -9, -9 };

int bfs(int sa, int sb, int sc);

int bfs(int sa, int sb, int sc) {
    queue<pair<int, pair<int, int>>> q;
    q.push({ sa, { sb, sc } });
    arr[sa][sb][sc] = 1;

    while (!q.empty()) {
        int a = q.front().first;
        int b = q.front().second.first;
        int c = q.front().second.second;
        int cnt = arr[a][b][c];
        q.pop();

        for (int i = 0; i < 6; i++) {
            int na = a + da[i];
            int nb = b + db[i];
            int nc = c + dc[i];

            if (na < 0) na = 0;
            if (nb < 0) nb = 0;
            if (nc < 0) nc = 0;

            if (arr[na][nb][nc] == 0) {
                q.push({ na, {nb, nc} });
                arr[na][nb][nc] = cnt + 1;
            }
        }
    }

    return arr[0][0][0];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);

    int N;

    cin >> N;
    for (int i = 0; i < N; i++) cin >> num[i];

    cout << bfs(num[0], num[1], num[2]) - 1 << '\n';

    return 0;
}

 

 3차원 배열의 각 칸은 SCV의 체력이 (a, b, c)로 남았을 때 공격당한 횟수를 의미한다.

 너비 우선 탐색에는 큐를 사용한다. 큐는 먼저 들어간 것이 먼저 나오고, 이미 방문한 칸은 다시 방문할 수 없기에 정렬을 하지 않아도 공격 횟수가 적은 칸부터 탐색하게 된다. 이를 이용하여 체력을 (0, 0, 0)으로 만드는 공격 횟수의 최솟값을 구했다.