BOJ 12869 : 뮤탈리스크

풀이 요약

BFS

풀이 상세

1. 세가지 공격에서 나타날 수 있는 총 경우의 수는 6가지이다. $_3P_3$

2. 삼차원 배열을 생성하여, scv 들이 현재 남은 데미지를 저장하며 탐색한다. 음수가 나올 수 있기에, 만약 체력이 scv 가 음수가 나올 경우는 0으로 업데이트 해주자.

3. scv 가 모두 체력이 0 인 경우에 도달 할 때가 답이 된다.

4. scv 가 1개, 2개만 있는 경우는 없는 scv 는 죽었다고 생각하고 0 부터 시작하면 된다.

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

using namespace std;
int N;
int visited[70][70][70];
struct S {
    int a, b, c;
};
vector<vector<int>> v = {{9, 3, 1},
                         {9, 1, 3},
                         {3, 9, 1},
                         {3, 1, 9},
                         {1, 9, 3},
                         {1, 3, 9}};
vector<int> scv;

void input() {
    cin >> N;
    scv = vector<int>(3, 0);
    for (int i = 0; i < N; i++) {
        cin >> scv[i];
    }
}

int bfs() {
    queue<S> q;
    q.push({scv[0], scv[1], scv[2]});
    visited[scv[0]][scv[1]][scv[2]] = 1;
    while (!q.empty()) {
        S curr = q.front();
        q.pop();
        if (visited[0][0][0]) break;
        for (int i = 0; i < 6; i++) {
            int na = (curr.a - v[i][0]) > 0 ? curr.a - v[i][0] : 0;
            int nb = (curr.b - v[i][1]) > 0 ? curr.b - v[i][1] : 0;
            int nc = (curr.c - v[i][2]) > 0 ? curr.c - v[i][2] : 0;
            if (visited[na][nb][nc]) continue;
            visited[na][nb][nc] = visited[curr.a][curr.b][curr.c] + 1;
            q.push({na, nb, nc});
        }
    }
    return visited[0][0][0] - 1;
}

void output() {
    cout << bfs();
}

int main() {
    input();
    output();
}