캐슬 디펜스

코드

#include <cstdio>
#include <vector>
#include <queue>
#include <iostream>
#include <cmath>
#include <algorithm>
#include <set>
#include <deque>
#include <numeric>
#include <map>
#define ll long long
using namespace std;
int N, M, D, ans;
int board[20][20];
int dc[4] = {0, 1, 0, -1};
int dr[4] = {1, 0, -1, 0};
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M >> D;
    for(int i=0;i<N;i++)
        for(int j=0;j<M;j++)
            cin >> board[i][j];

    int ch[M];
    fill(ch, ch+M, 1);
    for(int i=0;i<3;i++) ch[i] = 0;
    do{
        int tmp[N+1][M];
        int cnt=0;
        vector<int> arrow;
        /* board복사 */
        for(int i=0;i<N+1;i++)
            for(int j=0;j<M;j++)
                tmp[i][j] = board[i][j];
        /* 궁수 위치 선택 */
        for(int i=0;i<M;i++)
            if(ch[i] == 0) arrow.push_back(i);
        /* 디펜스 시작 */
        while(true)
        {
            /* 궁수 공격 */
            vector<pair<int,int>> delete_enemy(arrow.size());
            for(int i=0;i<delete_enemy.size();i++)
                delete_enemy[i] = {1e9,1e9};
            for(int n=0;n<arrow.size();n++)
            {
                int min_dist=1e9;
                for(int r=0;r<N;r++)
                {
                    for(int c=0;c<M;c++)
                    {
                        if(tmp[r][c] == 0) continue;
                        int dist = abs(r-N) + abs(c-arrow[n]);
                        if(dist > D) continue;
                        if(min_dist > dist){
                            delete_enemy[n] = {r,c};
                            min_dist = dist;
                        }else if(min_dist == dist and c < delete_enemy[n].second){
                            delete_enemy[n] = {r,c};
                        }
                    }
                }
            }
            /* 가까운 적들 삭제 */
            for(int i=0;i<delete_enemy.size();i++)
            {
                if(delete_enemy[i].first == 1e9) continue;
                if(tmp[delete_enemy[i].first][delete_enemy[i].second] == 1)
                {
                    tmp[delete_enemy[i].first][delete_enemy[i].second] = 0;
                    cnt++;
                }
            }
            /* 삭제되지 않고 살아남은 적 queue에 넣기 */
            queue<pair<int,int>> t_enemy;
            for(int i=N-1;i>=0;i--)
                for(int j=M-1;j>=0;j--)
                    if(tmp[i][j] == 1) t_enemy.push({i,j});
            /* 적이 더이상 없으면 디펜스 종료 */
            if(t_enemy.size() == 0) break;
            /* 적 이동 */
            while(!t_enemy.empty())
            {
                auto cur = t_enemy.front(); t_enemy.pop();
                int nr = cur.first + 1;
                int nc = cur.second + 0;
                tmp[cur.first][cur.second] = 0;
                if(nr>=N) continue;
                tmp[nr][nc] = 1;
            }
        }
        ans = max(ans, cnt);
    }while(next_permutation(ch, ch+M));
    cout << ans;
    return 0;
}

• 아쉬운 점
  • 문제를 보고 틀을 바로 잡아서 30분 정도면 풀 수 있을 것이라고 생각했는데 BFS에서 시간을 많이 보냄
  • 아쉽지만 그래도 문제유형이 조금씩 익숙해져가니까 희망이 보인다

• 오래걸린 이유
  • 현재 궁수의 위치에서 가장 가까운 적을 찾는 과정을 BFS로 구현했는데 이상하게 안됐다
    --> 그냥 2중 for문으로 모든 적에대해 dist를 비교하며 최소 위치의 적을 찾음
    (O(N)이 범위가 작아서 이렇게 했는데 컸다면 BFS로 해야했을 것임)