백준 12869 : 뮤탈리스크 (bfs)

bfs인데 visited가 3차원이였던 문제 

 

문제

수빈이는 강호와 함께 스타크래프트 게임을 하고 있다. 수빈이는 뮤탈리스크 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를 파괴하기 위한 공격 횟수의 최솟값을 출력한다.

예제 입력 1 복사

3
12 10 4

예제 출력 1 복사

2

예제 입력 2 복사

3
54 18 6

예제 출력 2 복사

6

예제 입력 3 복사

1
60

예제 출력 3 복사

7

예제 입력 4 복사

3
1 1 1

예제 출력 4 복사

1

예제 입력 5 복사

2
60 40

예제 출력 5 복사

9

 

• 풀이

 

처음에는 입력받은 scv로 순열을 구해서 방문하고 돌아가는 백트래킹 으로 구현해보려고 했지만 실패했고

bfs로 구현했다

 

뮤탈의 공격은 6종류로 들어올 수 있으니 아래 배열로 표현된다

int attack[6][3] = {{1,3,9},{1,9,3},{3,1,9},{3,9,1},{9,1,3},{9,3,1}};

 

scv들은 1~3대가 들어오고 각각 visited 배열의 인자로 생각해서 0,0,0이 될때까지 몇 번이 걸리는가를 bfs로 구하면된다

int visited[61][61][61] = {0,};

 

+ 계산이 벡터로 받기에는 너무 복잡해져서 struct를 사용해서 클래스처럼 .a .b .c로 꺼내는게 훨씬 편하다

struct A{
    int a, b, c;
};

 

bfs는 아래처럼 작성했고, na,nb,nc가 음수가 되면 배열 인덱스로 사용 불가능하고 파괴된것 = 0 으로 치면 되기에 max로 음수가 되지 않게 해줬다

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

 

- 전체 코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <tuple>

using namespace std;

int n;
vector<int> arr = {0,0,0};
int visited[61][61][61] = {0,};

//공격타입
int attack[6][3] = {{1,3,9},{1,9,3},{3,1,9},{3,9,1},{9,1,3},{9,3,1}};

//계산 편의용 struct
struct A{
    int a, b, c;
};

int res = 0;


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

int main() {
    cin >> n;

    for(int i = 0; i < n; i++){
        cin >> arr[i];
    }

    res = bfs(arr[0],arr[1],arr[2]);
    cout << res;

    return 0;
}