(코딩테스트) 백준-12896번 뮤탈리스크(bfs)

 

1) 문제 

 

문제

수빈이는 강호와 함께 스타크래프트 게임을 하고 있다. 수빈이는 뮤탈리스크 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.1)  입력조건

- 완전 탐색으로 풀수 있는가? :

- 최악의 조건으로 생각 했을 때 scv체력은 60,60,60

- 한마리는 계속 1씩 데미지를 받는다고 가정

- 시간복잡도는 6^10은 대략 6천만 >= 1천만 

  -> 중복된 요소를 줄이면서 탐색 필요

- dfs/bfs로 문제 풀이 

2.2)  풀이과정(bfs)(시간초과)

- bfs를 통해 최소 depth를 구하고, 최소 depth를 계속해서 갱신

- 시간초과 : 가장 마지막의 최소depth가 나오면 시간이 6천만번+원복시간 복잡도 계산 필요

2.3)  코드

#include <bits/stdc++.h>
using namespace std;

int n, scv[3], a[] = {-9,-3,-1}, cnt, min_attack, sum;
vector<int> v;
vector<vector<int>> li;

void go(int depth, int count){
    int flag = 0;
    for (int hp : scv){
        if (hp <= 0) {
            flag++;
        }
    }
    //전체가 0일때 최소 비교
    if(flag == 3){
        min_attack= min(min_attack,count);
        return ;
    }
    
    if (depth == min_attack){
        return;
    }
    
    for (int i = 0; i < li.size(); i++){
        for (int j = 0; j < n; j++){
            scv[j] += li[i][j];
            
        }
        cnt++;
        go(depth+1,cnt);
        for (int j = 0; j < n; j++){
            scv[j] -= li[i][j];
        }
        cnt--;
    }
}

int main(){
    cin >> n;
    for (int i = 0; i < n; i++){
        cin >> scv[i];
        sum += scv[i];
    }
    min_attack = sum / 13 + 1;
    do {
        for (int it : a){
            v.push_back(it);
        }
        li.push_back(v);
        v.clear();
    } while (next_permutation(a, a + 3));
    
    go(0,cnt);
    cout << min_attack;
}

3) 해설

3.1)  조건

- scv의 체력을 (x,y,z)라고 생각하면 3차원 공간에서 (0,0,0)까지 가는 최단거리

3.2)  사용된 알고리즘

- int형을 return 값으로 가지는 dfs

//3차원 좌표설정
struct A{
	int x,y,z;
};

queue<A> q;
q.push({x,y,z});  //큐를 만들어서 탐색 시작
visited[x][y][z] = 1;  //시작점 방문

while(q.size()){
	int a = q.front().a; //x좌표 대입
    int b = q.front().b; //y좌표 대입
    int c = q.front().c; //z좌표 대입
    q.pop();
    if(visited[0][0][0]) break; //최단거리로 도착했으므로 반복문 종료
    for (vector<int> iv : list){ //list는 데미지 순열
    	int na = a + iv[0]; //다음 x좌표 대입
        int nb = b + iv[1]; //다음 y좌표 대입
        int nc = c + iv[2]; //다음 z좌표 대입
        if(visited[na][nb][nc]) continue;
        visited[na][nb][nc] = visited[a][b][c] + 1; //다음 방문 노드의 거리 추가
        q.push({na,nb,nc}); //다음 노드 추가
    }
}

3.3)  완성된 코드

- int형을 return 값으로 가지는 dfs

#include <bits/stdc++.h>
using namespace std;

int n, a[64][64][64], visited[64][64][64], hp[3];
int de[3] = {-9, -3, -1};
vector<int> v;
vector<vector<int>> d;
struct A
{
    int a, b, c;
};
queue<A> q;

void make_list()
{
    do
    {
        for (int i : de)
        {
            v.push_back(i);
        }
        d.push_back(v);
        v.clear();
    } while (next_permutation(de, de + n));
}

int bfs(int x, int y, int z)
{
    visited[x][y][z] = 1;
    q.push({x, y, z});
    while (q.size())
    {
        int x = q.front().a;
        int y = q.front().b;
        int z = q.front().c;
        q.pop();
        if (visited[0][0][0])
            break;
        for (vector<int> iv : d)
        {
            int nx = max(0, x + iv[0]);
            int ny = max(0, y + iv[1]);
            int nz = max(0, z + iv[2]);
            if (visited[nx][ny][nz])
                continue;
            visited[nx][ny][nz] = visited[x][y][z] + 1;
            q.push({nx, ny, nz});
        }
    }
    return visited[0][0][0] - 1;
}

int main()
{
    cin >> n;
    for (int i = 0; i < 3; i++)
    {
        cin >> hp[i];
    }
    make_list();
    cout << bfs(hp[0], hp[1], hp[2]);
}