뮤탈리스크

이문제는 BFS이다.

나는 처음에 931 913 이런식으로 6가지경우의 수

순서에 상관있는 경우의 수니까

(next_permutation 사용해서 풀 수 도 있겠지만 일단 못품..)

순열이라고 생각을 했다.

근데 강의 들으니까

아! 싶었음.

가중치가 같고 한칸씩 움직일 때 최단거리 구할 때 BFS를 사용을 하는데

이런식으로 뮤탈이 때렸을 때의 상태값을

그래프화 해서 생각할 수도 있겠다라는 점을 깨달음.

즉

BFS로 풀 수 있는 이유가 뮤탈이 한번에 한번만 때리기 때문에 => "가중치"가 같다.

그럴때 최단 거리를 구할 수 있다!

체력이 모두 0이 되는 정점

cpp 코드

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <stack>
#include <algorithm>
using namespace std;
#define endl "\n"
#define MAX 1004
const int INF = 987654321;

int dp[64][64][64], a[3], n, visited[64][64][64];
int _a[6][3] =
{
    {9, 3, 1},
    {9, 1, 3},
    {3, 1, 9},
    {3, 9, 1},
    {1, 3, 9},
    {1, 9, 3}
};

// tuple대신 사용
struct A
{
    int a, b, c;
};

queue<A> q;
int Solve(int a, int b, int c)
{
    visited[a][b][c] = 1;
    q.push({a, b, c});
    while (!q.empty())
    {
        int a1 = q.front().a;
        int b1 = q.front().b;
        int c1 = q.front().c;
        q.pop();
         
        if (visited[0][0][0]) break;
        
        for (int i = 0; i < 6; ++i)
        {
            int na = max(0, a1 - _a[i][0]);
            int nb = max(0, b1 - _a[i][1]);
            int nc = max(0, c1 - _a[i][2]);
            if (visited[na][nb][nc]) continue;
            visited[na][nb][nc] = visited[a1][b1][c1] + 1;
            q.push({na, nb, nc});
        }
    }
    return visited[0][0][0] - 1;
}

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

    cin >> n;
    for (int i = 0; i < n; ++i)
    {
        cin >> a[i];
    }
    cout << Solve(a[0], a[1], a[2]) << endl;
    
    return 0;
}

배운 부분이 체력을 상태의 노드로 두어서

BFS로 visited를 3차원으로 사용해서

체력상태를 노드로 두고

레벨별로 탐색해 나간다...

또한

int na = max(0, a1 - _a[i][0]);
int nb = max(0, b1 - _a[i][1]);
int nc = max(0, c1 - _a[i][2]);

인덱스는 - 음수가 될 수 없기 때문에

이렇게 해준 부분도 꿀팁이다.