[17135번] 케슬 디펜스

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 구현

문제 해결을 위해 지문을 읽고 그대로 따라 내려가면 된다.

자세한 내용은 아래 주석을 통해 달아두었다.

소스 코드 : 

#include <iostream>
#include <cstdio>
#include <queue>
#include <algorithm>
#include <vector>
#include <cmath>
 
using namespace std;
 
typedef pair<int, int> pii;
 
int archer[3];
int arr[15][15];
int n, m, d;
 
vector<pii> enemy, etmp;
 
int y, x;
 
// 궁수와 가장 가까운 순서대로, 같다면 가장 왼쪽에 있는 순서대로 정렬
bool comp(const pii &a, const pii &b) {
    int d1 = abs(a.first - y) + abs(a.second - x);
    int d2 = abs(b.first - y) + abs(b.second - x);
    
    if (d1 == d2)
        return a.second < b.second;
 
    return d1 < d2;
}
pii solve(int here) {
    // y,x :: 궁수의 좌표
    y = n;
    x = archer[here];
 
    // 궁수 좌표를 기준으로 정렬
    sort(enemy.begin(), enemy.end(), comp);
 
    // 만약 가장 가까운 적이 d 이하이면 첫번째 적 리턴
    if (abs(enemy[0].first - y) + abs(enemy[0].second - x) <= d)
        return enemy[0];
 
    // 해당하는 적이 없음
    return { -1,-1 };
}
int main() {
    scanf("%d %d %d", &n, &m, &d);
 
    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
        {
            scanf("%d", &arr[i][j]);
            // 적이면 etmp에 좌표 push
            if (arr[i][j])
                etmp.push_back({ i,j });
        }
 
    int ans = 0;
    // 3중 포문으로 궁수 위치 지정
    for (int i = 0; i < m - 2; i++) {
        for (int j = i + 1; j < m - 1; j++) {
            for (int k = j + 1; k < m; k++) {
                archer[0] = i;
                archer[1] = j;
                archer[2] = k;
                int killCnt = 0;
 
                enemy = etmp;
                while (!enemy.empty()) {
                    // 이번 턴에 궁수가 죽이는 적을 kill 배열에 저장
                    pii kill[3];
                    for (int t = 0; t < 3; t++)
                        kill[t] = solve(t);
 
                    // 궁수가 죽인 적을 제외하고 tmp에 남은 적 push
                    // 이때 적의 좌표 + 1(아래로 이동)이 n 미만인것들만 push
                    vector<pii> tmp;
                    for (int a = 0; a < enemy.size(); a++) {
                        bool isKill = false;
                        for (int b = 0; b < 3; b++) {
                            if (enemy[a] == kill[b]) {
                                isKill = true;
                                break;
                            }
                        }
                        if (isKill) {
                            killCnt++;
                            continue;
                        }
                        if (enemy[a].first + 1 < n)
                            tmp.push_back({ enemy[a].first + 1, enemy[a].second });
                    }
 
                    ans = max(ans, killCnt);
 
                    enemy = tmp;
                }
            }
        }
    }
 
    printf("%d\n", ans);
 
    return 0;
}