[cpp 알고리즘] 백준 20005 보스몬스터 전리품

[백준] 20005 보스몬스터 cpp(c++) 풀이

알고리즘: 구현, 그래프 이론, 그래프 탐색, 시뮬레이션, 너비우선탐색

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

문제 요약

- 지도의 크기(M, N)과 플레이어의 수(P)가 주어진다. 

- 지도에는 .(이동할 수 있는 길), X(이동할 수 없는 길), 알파벳 소문자(플레이어 아이디), B(보스 몬스터) 위치가 주어진다.

- 각 플레이어의 아이디(알파벳 소문자)와 dps(1초당 얼만큼의 보스몬스터의 체력을 줄일 수 있는지)가 주어지고, 보스 몬스터의 HP가 주어진다.

- 모든 플레이어들은 보스몬스터의 위치로 최대한 빠른 경로로 이동하며, 이동한 경우 공격을 바로 시작한다. (공격에 소모되는 시간, 상/하/좌/우 한 칸을 이동하는 데 소요되는 시간은 모두 1초이다.) 

- 이 때, 보스가 죽기 전에 한 번이라도 보스를 공격한 플레이어 수의 최댓값을 구하는 문제이다. 

풀이 정리

크게 아래 2가지 단계로 나누어 접근했다.

(1) 각각의 플레이어가 보스몬스터의 위치로 최단 경로로 이동하기 => 최단 경로 이동에는 bfs를 사용했다.

(2) 보스몬스터의 위치로 도착한 이후에, 공격하기 

 

- bfs에서는 다음 위치가 보스의 위치라면 해당 times(몇 초 흘렀는지)를 리턴한 뒤에 shortest 배열에 넣었다.

- shortest 배열의 시간(초)를 줄여나가면서, 1초가 되었을 때는  공격하는 플레이어 수(answer)와 전체 플레이어들의 공격력(attackPOWER) 값을 증가 시켜 주었다.

- while 문을 반복하면서 누적 공격합(attackHP) 값도 계속 증가시켰다. 

 

C++ 코드

#include <iostream>
#include <vector>
#include <cstring>
#include <queue>
#include <tuple>
#define MAXM 1010
#define MAXN 1010
using namespace std;

int M, N, P, HP; // 세로 M, 가로 N, 플레이어 수 P, boss체력 HP
int arr[MAXM][MAXN];

int bossy, bossx;
vector<pair<int,int>> v; //플레이어 정보
int players[27]; //1~26번
int shortest[27]; //1~26번

int visited[MAXM][MAXN];

int dy[4] = {1, -1, 0, 0};
int dx[4] = {0, 0, 1, -1};
int bfs(int y, int x){
    memset(visited, 0, sizeof(visited));

    queue<tuple<int,int,int>> q;
    q.push({y,x,0});
    visited[y][x] = 1;
    
    while(!q.empty()){
        tuple<int,int,int> one = q.front();
        q.pop();
        
        int cy = get<0>(one);
        int cx = get<1>(one);
        int ctime = get<2>(one);
        
        for(int i=0; i<4; i++){
            int ny = cy + dy[i];
            int nx = cx + dx[i];
            
            if(ny<0 || ny>=M || nx<0 || nx >=N ) continue;
            if(visited[ny][nx] == 1) continue;
            if(arr[ny][nx] == 30){
                return ctime+1;
            }
            if(arr[ny][nx] >=0 && arr[ny][nx] <= 26){
                visited[ny][nx] = 1;
                q.push({ny, nx, ctime+1});
            }
        }
    }
    return -1;
}

int main(){
    cin >> M >> N >> P;
    for(int i=0; i<M; i++){
        for(int j=0; j<N; j++){
            char c; cin >> c;

            if(c=='.') arr[i][j] = 0;
            else if(c=='X') arr[i][j] = -1; //이동할 수 없는 길
            else if(c=='B'){
                bossy = i; bossx = j;
                arr[i][j] = 30;
            }
            else{
                arr[i][j] = (c-'a'+1); //1~26사이
                v.push_back({i, j}); //플레이어 위치
            }
        }
    }
    
    for(int i=0; i<27; i++) players[i] = -1;
    for(int i=0; i<P; i++){
        char c; int dps;
        cin >> c >> dps;
        players[c-'a'+1] = dps;
    }
    cin >> HP;
    
    //알파벳마다 최단거리 구하기
    for(int i=0; i<v.size(); i++){
        int time = bfs(v[i].first, v[i].second); // time초 후에 도달
        int alphabeti = arr[v[i].first][v[i].second];
        shortest[alphabeti] = time; // -1은 도달할 수 없음
    }
    
    int attackHP = 0;
    int attackPOWER = 0;
    int answer = 0;
    
    while(attackHP < HP){
        //알파벳마다 시간 줄어나감
        for(int i=0; i<v.size(); i++){
            int alphabeti = arr[v[i].first][v[i].second];
            if(shortest[alphabeti] == 1){
                shortest[alphabeti] = -1; //무시
                answer++;
                attackPOWER += players[alphabeti];
            }
            else if(shortest[alphabeti] >= 1){
                shortest[alphabeti]--; //1초씩 줄어든다.
            }
        }
        attackHP += attackPOWER;
        //cout << "현재 공격: " << attackPOWER << "누적 공격: " << attackHP << "\n";
    }
    cout << answer;
    
    return 0;
}

 

4%에서 틀렸습니다 (memset 사용 주의!)

#include <cstring>
memset(visited, 0, MAXM*MAXN);

 

- 처음에 memset 알고리즘의 헤더인 <cstring> 을 안써서 컴파일 오류가 발생했다.

- 또한 위에 코드처럼 마지막에 visited 배열의 크기를 적는 줄 알고 저렇게 썼다가 4%에서 틀렸습니다 가 계속 나왔다.

- sizeof(visited)를 사용하면 배열 visited의 실제 메모리 크기를 자동으로 계산해주기 때문에 이처럼 쓰는 게 더 낫다.