17135번 캐슬 디펜스

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

계속 제출해봐도 틀렸습니다가 뜨길래,

뭐가 문제인가 했었다.

생각해보니 내가 처음에 문제에 접근하였을 때는

문제 조건의 같은 적이 여러 궁수에게 공격당할 수 있다라는 조건을 읽고,

'최대'로 죽일 수 있는 적이라면, 당연히 1:1로 적을 죽여야 최댓값이 나올 수 있으니, 무시해도 되겠지라는

생각으로 구현했었다. 즉, 죽인 적을 즉시 0으로 바꿔주고, 다음 궁수가 무조건 다른 적을 죽일 수 있도록 구현하였었다.

그래서 위의 조건을 있는 그대로 그냥 받아드려서, 구현하고 제출하였더니 맞았다.

 

참고)

난 아래처럼, 죽일 적을 저장하고있었는데

if (dist <= min_dist && j <= x)
{
    kill = true;
    y = i; // 죽은 적의 자리 갱신
    x = j;
}

생각해보니 반례가 있었다.

5 5 5

1 1 1 1 1

1 1 1 1 1

1 1 1 1 1

1 1 1 1 1

1 1 1 1 1

일 경우, 최소 거리 조건은  D=5 이므로, if문에 의해 바로 눈 앞에 있는 적을 공격하는 것이 아니라

무조건 왼쪽을 공격해버리기 때문에 최소 거리 조건 D=5가 클 경우도 대비해야 한다.

#include <iostream>
#include <queue>
#include <stack>
#include <cstdio>
#include <vector>
#include <cstring>
#include <string>
#include <math.h>
#include <algorithm>
#include <map>
#include <set>
#include <sstream>
#include <tuple>
 
#pragma warning(disable:4996)  
#pragma comment(linker, "/STACK:336777216")
 
using namespace std;
 
typedef struct info
{
    int y;
    int x;
    int dist;
}info;
 
info temp;
 
int Map[20][20] = { 0, }, save[20][20] = { 0, }, N = 0, M = 0, D = 0, MAX = 0;
 
// save 배열은 초기 상태의 배열
// Map 배열은 game() 함수 내에서 진행할 때 변화하는 배열
 
bool use[20][20] = { false, }; // 궁수의 위치에 대한 백트래킹에 활용하는 배열
 
bool end_game() // 모든 Map 배열이 0이면 true(종료), 1이 하나라도 있으면 false(계속 진행)
{
    for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) if (Map[i][j] == 1) return false;
    return true;
}
 
bool cmp(const info & a, const info & b)
{
    if (a.dist == b.dist) return a.x < b.x;
    else return a.dist <= b.dist;
}
 
int game(vector<pair<int, int> > vc) // 디펜스 진행하는 함수
{
    int ret = 0, go = N;
 
    // ret는 죽은 적의 수
 
    while (go--) // 최대 N번 진행
    {
        if (end_game()) break; // Map 배열이 모두 0이면 break; 한후 return ret;
 
        vector<info> v;
 
        bool counter[20][20] = { false, };
 
        for (auto archer : vc) // 궁수의 위치는 vc vector 안에 저장되어 있음
        {
            bool kill = false; // 궁수가 정말로 적을 죽였는지 여부에 대한 bool 변수
 
            for (int i = N - 1; i >= 0; i--) // N - 1번 째 행부터 감소하면서 0번 째 행까지 검사한다.    
                for (int j = 0; j < M; j++)    // 열은 0부터 M - 1까지 검사
                    if (Map[i][j] == 1) // 만약 그 곳에 적이 있다면
                    {
                        int dist = abs(archer.first - i) + abs(archer.second - j);
                        // 일단 궁수와의 거리를 구한다.
 
                        if (dist > D) continue;
                        // 근데 문제 최고 거리 조건(=D)보다 초과한다면 다음 진행
 
                        temp.dist = dist;
                        temp.y = i;
                        temp.x = j;
 
                        v.push_back(temp);
                    }
            
 
            if (v.empty()) continue;
 
            if (v.size() >= 2) sort(v.begin(), v.end(), cmp);
 
            int ky = v.at(0).y;
            int kx = v.at(0).x;
 
            counter[ky][kx] = true;
 
            v.clear();
        }
 
        for (int i = 0; i < N; i++)
            for (int j = 0; j < M; j++)
                if (counter[i][j])
                {
                    ++ret;
                    Map[i][j] = 0;
                }
        
 
        for (int i = N - 1; i >= 0; i--) // 마찬가지로 N - 1번 ~ 0번 행을 감소하면서 검사.
            for (int j = 0; j < M; j++)    
                if (Map[i][j] == 1) // 아직 살아있는 적이 있다면
                {
                    if (i + 1 == N) Map[i][j] = 0; // 궁수 바로 1칸 위에 있는 적은 성으로 들어온다.
                    else // 그게 아니라면
                    {
                        Map[i + 1][j] = 1; // 한 칸 아래로 이동.
                        Map[i][j] = 0; // 그리고 이동 전의 칸은 0으로 바꿔줌.
                    }
                }
    }
 
    return ret;
}
 
void simulation(vector<pair<int, int> > vc, int pos)
{
    if (vc.size() == 3) // 궁수는 3마리 이므로
    {        
        for (int i = 0; i < N; i++) for (int j = 0; j < M; j++) Map[i][j] = save[i][j];
 
        MAX = max(MAX, game(vc));
 
        return;
    }
 
    for (int i = pos; i < M; i++) // 백트래킹
        if (!use[N][i]) // 궁수는 N번 째 행의 i번 째 열이다. 0 ~ N - 1번 째 행은 적의 위치
        {
            use[N][i] = true;
            vc.push_back({ N, i });
 
            simulation(vc, i);
 
            use[N][i] = false;
            vc.pop_back();
        }
}
 
int main(void)
{
    scanf("%d %d %d", &N, &M, &D);
 
    for (int i = 0; i < N; i++)
        for (int j = 0; j < M; j++)
        {
            scanf("%d", &save[i][j]);
 
            Map[i][j] = save[i][j];
        }
    
    vector<pair<int, int> > emp;
 
    simulation(emp, 0);
 
    printf("%d\n", MAX);
 
    return 0;
}