[백준 17135번] 캐슬 디펜스

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

17135번: 캐슬 디펜스

풀이) 

1. 궁수를 놓을 수 있는 위치를 dfs를 통해 조합을 구성한다.

2. 맵이 비었으면 게임이 종료시킨다.

3. 궁수들이 세팅이 되었다면 각 궁수들마다 잡을 적들을 세팅해서 queue에 넣어준다. (여러 궁수가 한 적을 노릴 수도 있어서)

4. 큐를 비우면서 적이면 죽인다.

5. 적을 이동시킨다.

#include <iostream>
#include <queue>
using namespace std;

int N, M, D, ans = 0;
int map[16][16], map_c[16][16];
int archorPosition[16];
int dir_x[3] = {0, -1, 0};
int dir_y[3] = {-1, 0, 1};
queue <pair<int, int> > attackList;

void copyMap()
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            map[i][j] = map_c[i][j];
}

int enemyEmpty()
{
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
            if (map[i][j])
                return (0);
    return (1);
}

void enemyMove()
{
    for (int i = N - 2; i > -1; i--)
    {
        for (int j = 0; j < M; j++)
        {
            map[i + 1][j] = map[i][j];
            if (i == 0)
                map[i][j] = 0;
        }
    }
}

void addEnemy(int i)
{
    queue <pair <pair<int, int>, int> > enemyPostion;
    pair <pair<int, int>, int> start = make_pair(make_pair(N - 1, i), 1);
    enemyPostion.push(start);
    while (!enemyPostion.empty())
    {
        pair <pair<int, int>, int> front = enemyPostion.front();
        enemyPostion.pop();
        if (map[front.first.first][front.first.second] == 1)
        {
            attackList.push(make_pair(front.first.first, front.first.second));
            break ;
        }
        if (front.second + 1 <= D)
        {
            for (int i = 0; i < 3; i++)
            {
                int nx = front.first.first + dir_x[i];
                int ny = front.first.second + dir_y[i];
                if (nx < 0 || ny < 0 || ny > M - 1)
                    continue ;
                enemyPostion.push(make_pair(make_pair(nx, ny), front.second + 1));
            }
        }
    }
    while (!enemyPostion.empty())
        enemyPostion.pop();
}

void gameStart()
{
    int kill = 0;
    while (1)
    {
        if (enemyEmpty())
            break ;
        for (int i = 0; i < M; i++)
        {
            if (archorPosition[i])
                addEnemy(i);
        }
        while (!attackList.empty())
        {
            pair<int, int> front = attackList.front();
            attackList.pop();
            if (map[front.first][front.second] == 1)
            {
                map[front.first][front.second] = 0;
                kill++;
            }
        }
        enemyMove();
    }
    ans = kill > ans ? kill : ans;
}

void dfs(int idx, int cnt)
{
    if (idx > M - 1)
        return ;
    if (cnt == 3)
    {
        copyMap();
        gameStart();
        return ;
    }
    archorPosition[idx + 1] = 1;
    dfs(idx + 1, cnt + 1);
    archorPosition[idx + 1] = 0;
    dfs(idx + 1, cnt);
}

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 >> map_c[i][j];
    
    for (int i = 0; i < M - 2; i++)
    {
        archorPosition[i] = 1;
        dfs(i, 1);
        archorPosition[i] = 0;
    }

    cout << ans << "\n";
}

 

 

제 코드는 절대 완벽하지 않습니다

더 좋은 풀이방법 혹은 코드에 관한 질문이 있으시면 언제든 댓글주세요!