12869 : 뮤탈리스크 - BFS, DP

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

12869번: 뮤탈리스크

문제요약

hp가 0이 될 때까지 공격 최소 횟수

 

난이도

Gold 4

---

풀이 포인트

• Struct 사용법

// 세 개 부터는 튜플인데, 귀찮으니 struct
struct A{
    int a,b,c;
};

queue<A>q;

• 그래프로  치환하여 생각하기

• 음수 막아주는 코드

int na = max(0, a - _a[i][0]);
int nb = max(0, b - _a[i][1]);
int nc = max(0, c - _a[i][2]);

• 3차원 배열이든, 2차원 배열이든 결국 한 점에 도달하기 위한 지도

---

REVIEW

 

첫번째 생각했던 아이디어는,

남은 hp를 내림차순 정렬 후, 9,3,1 순으로 빼주는 것. 즉 큰 숫자 부터 큰 값을 빼주는 것이었다.

테스트 케이스 5개는 통과, 나머지 하나는 통과하지 않는 아이디어였다.

 

그리고서, 9,3,1을 순열로 나열해, 차례로 빼줘 보자고 생각하고

또 재귀함수로 뻗어나가는 꼴을 생각했는데 또 그 스케일에 무너져서 포기함.

 

모범 답안에서 배워야 할 것 첫 번째. struct 자료 구조의 사용.

늘상 내가 원하는 구조의 자료구조를 딱 알맞게 설정하는 것이 어려운데,

pair를 넘어서는 구조가 특히 고민이되는 순간이 많았다. 지피티에 물어보면 튜플의 사용법을 알려줬는데 이런 방법이!

 

struct를 선언하고 queue에 그 구조체를 담아 사용하는 방법.

 

두번째, 그래프로 치환해서 생각하기.

이 문제를 bfs로 치환해 생각한다는 것이 꽤나 충격이었다.

미연시나 선택에 따라 다른 결말에 도달하는 느낌의 경우의 수를 그래프 모양으로 상상할 수 있어야 한다.

이 문제의 경우에도 6가지 순열에 따라 나타나는 다른 결과값을 하나의 노드, 또 그 노드에서 6가지로 뻗어나가는 엣지로 이루어진

그래프로 치환하여 생각하는 것이 중요.

 

내가 계속해서 재귀를 떠올리는 것을 재귀 구현이 아닌 그래프 구현 후 탐색 방법 생각으로 이어지게끔 하면 될 것 같다.

 

그래프로 바꿔 생각한 후에는 최단거리 bfs문제가 되어버린다.

 

참 또 간단한 수학 문제인듯한데 코드 구현이 어려워 막막했다가 여러가지를 배웠다.

 

---

CODE

 

#include <bits/stdc++.h> 
using namespace std;
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}
};
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.size()){
        int a = q.front().a; 
        int b = q.front().b; 
        int c = q.front().c; 
        q.pop();
        if(visited[0][0][0]) break;
        for(int i = 0; i < 6; i++){
            int na = max(0, a - _a[i][0]);
            int nb = max(0, b - _a[i][1]); 
            int nc = max(0, c - _a[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;   
}
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]) << "\n"; 
    return 0;
}