백준17135 캐슬디펜스

2020.02.18

백준17135 캐슬디펜스

풀이

• 궁수 위치 3개를 뽑는 경우의 수를 조합으로 찾는다.

• simulation을 이용해 그 때 제거한 적의 수를 구하고 경우의 수 중 최댓값을 찾는다.

• 변수

  • inMap : 초기 map 상태
  • nextMap : 게임을 진행하면서 변화하는 map
  • length : 각 열에서 가장 위에있는 적부터 옮길 수 있도록 하기 위해서 맨 위 행 번호를 기록한 변수
  • nextLen : 초기 길이 변수 만큼만 적을 옮기도록 최적화하기 위해 변화하며 사용할 length 변수
  • check : 처음 input에서 이미 담은걸 안담도록 만들기 위해 사용한 변수

• 함수

  • search : 궁수의 위치를 받아서 제거할 수 있는 적의 위치를 반환하는 함수
  • kill : 궁수가 적을 제거하는 함수
  • move : 적이 이동하는 함수
  • simulate : 궁수 위치의 조합이 완성되면 게임을 진행해서 제거할 수 있는 적을 반환하는 함수
  • getResult : 궁수 위치의 조합을 결정하고 제거할 수 있는 적의 최대 수를 반환하는 함수

• input을 받으면서 각 열의 가장 윗쪽 적의 index를 length 배열에 저장, 그 중 가장 윗쪽에 있는 적의 index를 T에 저장.

• 이걸 이용해서 move와 simulate에서 simulation을 최소한으로 돌릴 수 있도록 한다.

• kill에서는 search 함수를 이용해서 가장 가까우면서 가장 왼쪽에 있는 적을 찾고 그에 따라 적을 제거한다.

  (이미 제거되었으면 제거하지 않으며 제거한 숫자를 세서 반환한다.)

코드

//! 2020.02.18
// TODO BJ17135_캐슬디펜스
#include<cstdio>
#include<vector>
using namespace std;

const int MAX = 20;
int N, M, D;
int inMap[MAX][MAX];
int nextMap[MAX][MAX];
int length[MAX];
int nextLen[MAX];
bool check[MAX];
int T;
int army[3];

bool inRange(int y, int x) {
    if(y >= 0 && y < N && x >= 0 && x < M) return true;
    else return false;
}

pair<int, int> search(int y, int x) {
    pair<int, int> ret = make_pair(-1, -1);
    for (int d = 0; d < D; d++) {
        for (int j = x - d; j <= x + d; j++) {
            int i;
            if(j<=x) i = x + y - d - j;
            else i = y - (x + d -j);
            if (inRange(i,j) && nextMap[i][j] == 1) {
                ret.first = i;
                ret.second = j;
                return ret;
            }
        }
    }
    return ret;
}

int kill() {
    vector <pair<int, int>> myV;
    for (int k = 0; k < 3; k++) {
        int px = army[k];
        int py = N - 1;
        myV.push_back(search(py, px));
    }
    int killCnt = 0;

    for (int k = 0; k < 3; k++) {
        int y = myV[k].first;
        int x = myV[k].second;
        if (y != -1 && nextMap[y][x] > 0) {
            nextMap[y][x] -= 1;
            killCnt++;
        }
    }
    return killCnt;
}

void move() {
    for (int j = 0; j < M; j++) {
        for (int i = N - 1; i >= nextLen[j]+1; i--) {
            nextMap[i][j] = nextMap[i - 1][j];
        }
        if (nextLen[j] < N) {
            nextMap[nextLen[j]][j] = 0;
            nextLen[j]++;
        }
    }
}

int simulate() {
    int ret = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            nextMap[i][j] = inMap[i][j];
        }
        for(int j=0;j<M;j++) nextLen[j] = length[j];
    }

    for (int t = T; t <= N; t++) {
        ret += kill();
        move();
    }

    return ret;
}

int getResult(int idx,int prev) {
    if (idx >= 3) return simulate();
    else {
        int maxRet = -1;
        for (int j = prev + 1; j < M; j++) {
            army[idx] = j;
            int tmpRet = getResult(idx + 1, j);
            if (tmpRet > maxRet) maxRet = tmpRet;
        }
        return maxRet;
    }
}

int main() {
    scanf("%d %d %d", &N, &M, &D);
    T = -1;
    for (int j = 0; j < M; j++) length[j] = N-1;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < M; j++) {
            scanf("%d", &inMap[i][j]);
            if (inMap[i][j] == 1) {
                if (T == -1) T = i;
                if (!check[j]) {
                    check[j] = true;
                    length[j] = i;
                }
            }
        }
    }
    printf("%d\n", getResult(0,-1));
    return 0;
}

실수

1. 가장 큰 실수는 kill에서 index를 처리할 때 마름모의 반(세모)로 처리했어야 했는데 index 처리를 잘못해서 대각선으로 처리하도록 만들어버렸었다. 기준점 좌, 우로 i와 j의 관계가 다른데 같게 처리한 것이 문제였다.
2. length가 변한다는 걸 인지하지 못해서 첫번째 이후 simulation 잘못된 결과가 나왔다. 또, T에 따라 simulation을 진행하는 횟수를 잘못 처리했다. 이런 것들은 최적화를 하려다보니 나온 실수인데, 완전탐색으로 모든 경우를 봤어도 충분한 문제였고 이를 먼저 구현한 후에 최적화를 시도했다면 이런 실수를 방지할 수 있었지 않을까 싶다. 아직 최적화는 부족함이 많은 것 같은데 연습이 더 필요한 것 같고, 확실히 코드의 속도는 빨랐다.