백준 17135. 캐슬 디펜스

17135. 캐슬 디펜스

• 브루트포스 + 시뮬레이션 문제였다.
• 문제에 써있는 내용대로 궁수 3명의 위치를 선택 후 시뮬레이션을 진행하여 풀면 된다.

풀이 과정

1. 궁수 3명의 위치를 선택한다. (go 함수)
2. 적을 공격하고 적이 이동하도록 시뮬레이션해준다. (Simulate 함수)
   1. 궁수는 자신으로부터 거리가 D이하인 적 중에서 가장 가까운 적을 공격한다.
   2. 거리가 가까운 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다.
3. 모든 적이 맨 아래로 이동하여 제외될때까지 반복한다.
4. 1~3 과정을 반복한다.

소스코드

#include<iostream>
#include<algorithm>
#include<vector>

using namespace std;

int map[16][16];
int n, m, d;
int ch[3];
int ans;
int endLine=-1; // 최초 상태에 적이 있는 가장 높은 곳
vector<pair<int, int>> shotPos; // 궁수가 쏜 좌표를 모아논곳

// 두점의 거리를 구하는 함수
int GetDistance(int x1, int y1, int x2, int y2)
{
    int x = x1 - x2 > 0 ? x1 - x2 : x2 - x1;
    int y = y1 - y2 > 0 ? y1 - y2 : y2 - y1;
    return x + y;
}

void Simulate()
{
    int cnt = 0;
    int sum = 0;
    // 맵 복사
    int tmpMap[16][16];
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            tmpMap[i][j] = map[i][j];
        }
    }

    // 맨 위의 적이 다 내려올때까지 반복
    while (cnt< endLine)
    {
        shotPos.clear();
        // 궁수가 먼저 공격
        for (int i = 0; i < 3; i++)
        {
            int shotX = 20;
            int shotY = 20;
            int tmpDist = d;
            for (int j = n - 1; j >= 0; j--)
            {
                for (int k = 0; k < m; k++)
                {
                    // 거리가 작으면 무조건 선택
                    if (tmpMap[j][k] == 1 && 
                        GetDistance(j, k, n, ch[i]) < tmpDist)
                    {
                        tmpDist = GetDistance(j, k, n, ch[i]);
                        shotX = j;
                        shotY = k;
                    }
                    // 거리가 같을땐 가장 왼쪽
                    else if (tmpMap[j][k] == 1 && 
                            GetDistance(j, k, n, ch[i]) == tmpDist)
                    {
                        if (k < shotY)
                        {
                            shotX = j;
                            shotY = k;
                        }
                    }
                }
            }
            // 궁수가 쏜 위치가 갱신되어있는 상태라면 추가
            if (shotX != 20 && shotY != 20)
            {
                shotPos.push_back({ shotX,shotY });
            }
        }

        // 궁수가 쏜 포지션들에 대해 반복
        for (int i = 0; i < shotPos.size(); i++)
        {
            // 중복된 지점을 쐈을땐 1만 증가해야하므로 아래 조건 추가
            if (tmpMap[shotPos[i].first][shotPos[i].second] == 1)
            {
                tmpMap[shotPos[i].first][shotPos[i].second] = 0;
                sum++;
            }

        }

        // 적 이동
        for (int i = n-1; i >=1; i--)
        {
            for (int j = 0; j < m; j++)
            {
                tmpMap[i][j] = tmpMap[i - 1][j];
            }
        }
        for (int i = 0; i < m; i++)
        {
            tmpMap[0][i] = 0;
        }
        cnt++;
    }

    // 최댓값이라면 갱신
    ans = max(ans, sum);
}

// 궁수 3명을 놓을 위치 선택
void go(int cnt,int idx)
{
    if (cnt == 3)
    {
        Simulate();
        return;
    }

    for (int i = idx; i < m; i++)
    {
        ch[cnt] = i;
        go(cnt + 1, i + 1);
    }
}

int main()
{
    cin >> n >> m >> d;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < m; j++)
        {
            cin >> map[i][j];
            if (map[i][j] == 1 && endLine==-1)
            {
                endLine = n-i;
            }
        }
    }

    go(0,0);
    cout << ans << endl;
    return 0;
}

전체 소스 코드