[백준][C++] 17135 캐슬 디펜스

 

 

 

알고리즘 종류

    - 구현

    - BFS

 

 

 

사고 과정

    1. 궁수의 배치를 조합으로 구한다.

    2. 궁수가 공격할 적군의 위치를 구하고(중복 가능) 제거한다. 그리고 적군을 이동시킨다.

    3. 2번을 한 세트로 해서 계속 돌리다가 적군이 0이 되면 반복을 멈춘다.

    4. 궁수가 죽인 적군의 수를 갱신한다.

    5. 1번에서 구한 다른 궁수의 배치로 2번부터 시작한다.

 

 

 

구현(C++)

#include <iostream>
#include <stdio.h>
#include <vector>
#include <queue>
#include <cstring>
#include <map>
#include <algorithm>
 
using namespace std;
 
int n, m, d;
int killed=0, enemies=0;
int tmpKilled, tmpEnemies;
 
int dir[4][2] = {{1,0}, {0,1}, {-1,0}, {0,-1}};
 
int mat[20][20];
int mat2[20][20];
// BFS를 위한 배열  
int isVisited[20][20];
// 조합을 위한 배열  
int location[20];
 
// 궁수는 같은 적군을 죽일 수 있다. 중복을 해결하기 위하여 map을 이용한다.  
map<pair<int, int>, int> enemyLocations;
 
bool isValid(int y, int x){
    return (y>=0 && y<n) && (x>=0 && x<m);
}
 
bool cmp(pair<int, int> a,  pair<int, int> b){
    return a.second < b.second;
}
 
// 적군이 움직인다.  
void move(){
    for(int i=n-1; i>=0; i--){
        for(int j=m-1; j>=0; j--){
            if(mat2[i][j] == 0) continue;
            // 성벽에 닿으면 적군의 수는 감소한다.  
            if(!isValid(i+1, j)){
                mat2[i][j] = 0;
                tmpEnemies --;
            }
            else {
                mat2[i][j] = 0;
                mat2[i+1][j] = 1;
            }
        }
    }
}
 
// 궁수 1명당 공격할 적군을 찾는다. BFS이용  
void attack(int y, int x){
    memset(isVisited, 0, sizeof(isVisited));
    vector<pair<int, int> > tmp_v;
    queue<pair<int, int> > q;
    int dist = 1;
    
    q.push({y, x});
    
    while(!q.empty()){
        // 궁수의 사거리를 넘으면 멈춘다.  
        if(dist > d) break;
        
        int size = q.size();
        tmp_v.clear();
        
        for(int i=0; i<size; i++){
            int hx = q.front().second;
            int hy = q.front().first;
            q.pop();
 
            for(int d=0; d<4; d++){
                int nx = hx + dir[d][0];
                int ny = hy + dir[d][1];
                                
                if(isVisited[ny][nx]) continue;
                if(!isValid(ny, nx)) continue;
                
                isVisited[ny][nx] = 1;
                q.push({ny, nx});
                
                if(mat2[ny][nx]){
                    tmp_v.push_back({ny,nx});
                }
                
            }
        }
 
        // 같은 거리 내에 적군이 여러 명이면 정렬하여 가장 왼쪽 적군을 표적으로 한다. 
        if(tmp_v.size() > 0){
            sort(tmp_v.begin(), tmp_v.end(), cmp);
            enemyLocations[{tmp_v[0].first,  tmp_v[0].second}] = 1;
            return;
        }
        
        dist ++;
    }
}
 
// 정해진 궁수의 위치에서 전투  
void combat(){
    // 맵 복사, 궁수가 킬 수, 적군의 수 초기화  
    memcpy(mat2, mat, sizeof(mat));
    tmpKilled = 0;
    tmpEnemies = enemies;
    
    // 궁수의 위치 vector에 넣기  
    vector<int> v;
    for(int i=0; i<m; i++){
        if(location[i] == 0) continue;
        v.push_back(i);
    }
 
    // 궁수 공격 + 적군의 움직임이 한 세트로 동작한다.  
    while(1){
        enemyLocations.clear();
        if(tmpEnemies == 0) break;
        
        // archor attack
        for(int i=0; i<3; i++){
            int x = v[i];
            int y = n;
            attack(y, x);
        }
        
        // remove enemies
        map<pair<int, int>, int> ::iterator iter;
        for(iter = enemyLocations.begin(); iter != enemyLocations.end(); iter++){
            mat2[iter->first.first][iter->first.second] = 0;
            tmpKilled++;
            tmpEnemies--;
        }
 
        // enemies move
        move();
    }
    
    if(tmpKilled > killed) killed = tmpKilled;
    
}
 
// 조합으로 궁수의 위치 알기 (중복X, 순서 O) 
void combination(int cur, int cnt){
    if(cnt == 3){
        combat();
    }
    
    for(int i=cur; i<m; i++){
        if(location[i]) continue;
        location[i] = 1;
        combination(i, cnt+1);
        location[i] = 0;
    }
}
 
 
void solution(){
    combination(0, 0);
}
 
int main(void){
    
    cin >> n >> m >> d;
    
    // 상태 입력 받기, 적군의 수 세기  
    int state;
    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> state;
            mat[i][j] = state;
            if(state) enemies++;
        }
    }
    
    solution();
    
    cout << killed << endl;
}
 
 

 

 

 

시행착오

    - 궁수가 중복된 적을 죽일 수 있다는 것을 간과했다. 코드를 보고 문제 내용을 다시 보느라 40분을 사용했다.

    - 중복을 제거하는 방법은 중요하다. 구현 문제에서 중복된 것을 제거하는 과정이 많이 나온다. '동시에'라는 단어가 나오면 주의해야 할 것 같다. 동시에 동작하면 같은 타겟을 중복해서 처리할 수 있기 때문이다. 이전에 상어 문제의 경우 2차원 배열에 체크해서 중복된 상어를 잡았던 것 같다. 여기서는 map을 이용해 봤다. map도 나쁘지 않은 것 같다. 적재적소하게 사용해야겠다.