캐슬 디펜스

• 문제

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

17135번: 캐슬 디펜스

• 코드

#include <iostream>
#include <vector>
#include <cmath>
#include <unordered_map>
#include <algorithm>

using namespace std;

int N, M, D;

bool arr[15][15];

bool check[15];

int max_val = 0;

bool isWin(bool myArr[15][15]){
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++){
            if(myArr[i][j])
                return false;
        }
    }
    return true;
}

bool isLost(bool myArr[15][15]){
    for(int j=0; j<M; j++){
        if(myArr[N-1][j])
            return true;
    }
    return false;

}

void printArr(bool myArr[15][15]){
    for(int i=0; i<N; i++){
        for(int j=0; j<M; j++)
            cout << myArr[i][j] << ' ';
        cout << '\n';
    }
    cout << '\n';

}

int killCount(){

    bool myArr[15][15];
    for(int i=0; i<15; i++){
        for(int j=0; j<15; j++)
            myArr[i][j] = arr[i][j];
    }
    
    vector<vector<int>> archerPos;

    for(int i=0; i<M; i++){
        if(check[i]){
            archerPos.push_back(vector<int>{N, i});
        }
    }

    bool killCheck[15][15];
    int killCount = 0;

    while(true){
        // printArr(myArr);
        for(int i=0; i<15; i++){
            for(int j=0; j<15; j++){
                killCheck[i][j] = false;
            }
        }

        vector<vector<int>> enemyPos;

        for(int i=N-1; i>=0; i--){
            for(int j=0; j<M; j++){
                if(myArr[i][j])
                    enemyPos.push_back(vector<int>{i,j});
            }
        }

        for(auto archer : archerPos){
            int a_r = archer[0];
            int a_c = archer[1];
            int curDist = 2e9;
            vector<int> nearEnemy;
            for(auto enemy : enemyPos){
                int e_r = enemy[0];
                int e_c = enemy[1];
                int dist = (int)abs(a_r-e_r) + (int)abs(a_c-e_c);
                if(D >= dist && curDist > dist){
                    nearEnemy = enemy;
                    curDist = dist;
                }else if(D >= dist && curDist == dist){
                    if(nearEnemy[1] > enemy[1]){
                        nearEnemy = enemy;
                        curDist = dist;
                    }
                }
            }
            if(nearEnemy.size() != 0)
                killCheck[nearEnemy[0]][nearEnemy[1]] = true;
        }

        for(int i=0; i<N; i++){
            for(int j=0; j<M; j++){
                if(killCheck[i][j]){
                    myArr[i][j] = false;
                    killCount++;
                }
            }
        }

        //종료 조건인지 판단 
        //1. 모두 죽임

        if(isWin(myArr)){
            break;
        }else{
            for(int j=0; j<M; j++)
                myArr[N-1][j] = 0;
            for(int j=0; j<M; j++){
                for(int i=N-1; i>=1; i--)
                    swap(myArr[i][j], myArr[i-1][j]);
            }
        }
    }
    // printArr(myArr);

    return killCount;

}

void dfs(int curIdx, int leftArcher){

    if(leftArcher == 0){

        max_val = max(max_val, killCount());

    }else if(curIdx == M){
        return;
    }else{

        check[curIdx] = true;
        dfs(curIdx+1, leftArcher-1);
        check[curIdx] = false;

        dfs(curIdx+1, leftArcher);

    }

}

int main(){

    cin >> N >> M >> D;

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

    dfs(0, 3);

    cout << max_val << '\n';

}

• 피드백
  • 실수를 했다.
  • 조건 '가장 왼쪽의 적'을 내가 현재의 myArr에서 N의 역순, M의 순으로 탐색해서 당연히 가장 왼쪽의 적부터 탐색하고 변동이 없을 것이라 생각했는데 다음과 같은 반례가 있다.
  • 아래와 같은 상황에서 2번 째 줄의 적을 탐색하고 더 이상 변동되지 않는다... 이는 오류
  • 담 부터는 스스로 자명하다 생각하는 상황이더라도 무조건 조건식을 구현해서 실수를 미리 방지해야겠다.

0 0 1 0 0
0 0 0 1 0
0 0 0 0 0