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

안녕하세요! 오늘은 코딩테스트 문제 중 하나인 "뮤탈리스크" 문제를 해결하는 방법에 대해 설명하려고 합니다. 이 문제는 뮤탈리스크가 남은 SCV를 모두 파괴하는 문제입니다. 문제를 해결하는 과정과 코드를 자세히 알아보겠습니다.

문제링크:

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

12869번: 뮤탈리스크

Q

문제개요

스타크래프트 게임에서 뮤탈리스크가 남은 SCV를 모두 파괴하는 문제입니다. SCV는 1~3개까지 있으며, 각각의 체력이 주어집니다. 뮤탈리스크는 한 번의 공격으로 최대 세 개의 SCV를 동시에 공격할 수 있으며, 첫 번째 SCV는 9의 체력을, 두 번째 SCV는 3의 체력을, 세 번째 SCV는 1의 체력을 잃습니다. 목표는 모든 SCV를 파괴하기 위한 최소 공격 횟수를 찾는 것입니다.

해결전략

이 문제는 모든 가능한 공격 조합을 고려하여 최소 공격 횟수를 찾아야 합니다. 여기서 동적 프로그래밍(Dynamic Programming, DP)과 너비 우선 탐색(Breadth-First Search, BFS)을 결합한 방식을 사용합니다. 각 SCV의 체력 상태를 나타내는 3차원 배열을 사용하여 방문한 상태를 체크하고, BFS를 사용하여 가능한 모든 상태를 탐색합니다.

코드 구현

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

using namespace std;

// 각 SCV의 체력에 따른 최소 공격 횟수를 저장할 3차원 배열
int dp[64][64][64], scvs[3], visited[64][64][64];

// 뮤탈리스크가 공격할 때 각 SCV에 대한 데미지 배열
int dmg[6][3] = {{9, 3, 1}, {9, 1, 3}, {3, 1, 9}, {3, 9, 1}, {1, 3, 9}, {1, 9, 3}};

// SCV의 상태를 저장할 구조체
struct A {int a, b, c;};

// SCV의 개수
int n;

// BFS 탐색을 위한 큐
queue<A> q;

// 모든 SCV를 파괴하기 위한 최소 공격 횟수를 계산하는 함수
int attack(int a, int b, int c) {
    // 방문 배열 초기화
    visited[a][b][c] = 1;
    q.push({a, b, c});
    while (!q.empty()) {
        int a = q.front().a, b = q.front().b, c = q.front().c;
        q.pop();
        for (int i = 0; i < 6; i++) {
            // 다음 상태로 이동할 때의 SCV 체력 계산
            int na = max(0, a - dmg[i][0]), nb = max(0, b - dmg[i][1]), nc = max(0, c - dmg[i][2]);
            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; // 모든 SCV가 파괴된 상태의 공격 횟수 반환
}

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

    // SCV 개수와 체력 입력 받기
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> scvs[i];
    }

    // 최소 공격 횟수 출력
    cout << attack(scvs[0], scvs[1], scvs[2]) << "\n";
}

코드 설명

이 코드는 SCV를 파괴하기 위한 최소 공격 횟수를 BFS를 사용하여 찾습니다. 각 상태는 SCV의 체력 조합으로 나타나며, visited 배열을 사용하여 각 상태를 최소한으로 방문하도록 합니다. 가능한 모든 공격 조합(dmg 배열)을 적용해보며, SCV의 체력이 0 이하가 되면 해당 SCV가 파괴된 것으로 간주합니다. BFS 탐색을 통해 모든 SCV가 파괴된 상태(0, 0, 0)에 도달할 때까지 탐색을 반복하며, 이때까지의 공격 횟수를 반환합니다.

결론

이 문제는 DP와 BFS를 결합하여 해결할 수 있으며, 이 접근법은 다양한 상태 공간 탐색 문제에 적용될 수 있습니다. 본 문제에서는 모든 가능한 공격 조합을 시뮬레이션하여, 주어진 조건 내에서 최소 공격 횟수를 효율적으로 찾아냅니다. 이 방법은 복잡한 문제를 단계별로 나누어 해결하는 동적 프로그래밍의 원리와, 넓은 범위의 상태를 체계적으로 탐색하는 BFS의 장점을 결합한 것입니다.