백준 17135번 캐슬 디펜스 문제 풀이

문제 설명

캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 N×M인 격자판으로 나타낼 수 있다. 격자판은 1×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나이다. 격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다.

성을 적에게서 지키기 위해 궁수 3명을 배치하려고 한다. 궁수는 성이 있는 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다. 각각의 턴마다 궁수는 적 하나를 공격할 수 있고, 모든 궁수는 동시에 공격한다. 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다. 같은 적이 여러 궁수에게 공격당할 수 있다. 공격받은 적은 게임에서 제외된다. 궁수의 공격이 끝나면, 적이 이동한다. 적은 아래로 한 칸 이동하며, 성이 있는 칸으로 이동한 경우에는 게임에서 제외된다. 모든 적이 격자판에서 제외되면 게임이 끝난다. 

게임 설명에서 보다시피 궁수를 배치한 이후의 게임 진행은 정해져있다. 따라서, 이 게임은 궁수의 위치가 중요하다. 격자판의 상태가 주어졌을 때, 궁수의 공격으로 제거할 수 있는 적의 최대 수를 계산해보자.

격자판의 두 위치 (r1, c1), (r2, c2)의 거리는 |r1-r2| + |c1-c2|이다.

문제를 보고 든 생각

• 궁수를 각 열마다 한 명씩 배치해서 결과가 가장 큰 것을 출력하면 되겠다.
• 한 명씩 가장 가깝고 왼쪽에 있는 적을 죽이면 되겠다. (이러면 안된다. 한 번에 같은 적을 쏠 수도 있기 때문이다.) 그러면 이게 왜 최대로 많은 적을 죽이는 방법인지 이해할 수 없다 ¸◕ˇ‸ˇ◕˛ 
• 기능별로 함수를 잘 나눠야겠다.

풀이 간단 설명

1. 한 번에 같은 적을 쏘기 때문에 적의 정보를 담은 2차원 배열을 복사해서 그 곳에 중간 과정을 저장한다.
2. 최단 경로를 구하되 방향은 세 방향만 잡았다. (좌 상 우) 아래로 내려갈 일이 없기 때문이다.
3. 왼쪽 먼저 최단 경로를 탐색하는데 (너비 우선 탐색) 적이 있다면 바로 적의 위치와 거리를 반환한다. (같은 거리라면 왼쪽의 적을 우선적으로 죽이기 때문)
4. 이미 죽은 적이라도 위의 조건과 부합하면 또 쏜다. (확인사살)
5. 죽인 적의 수를 카운팅 한다.
6. 이걸 열의 번호가 (0, 1, 2)부터 (M-3, M-2, M-1)까지 순회한다.

코드

#include <iostream>
#include <queue>

#define MAX_N 15

using namespace std;

struct strt{
  int r, c;
  int dist;
};


int N, M, D;
int ene[MAX_N+1][MAX_N+1];
int dir[3][2] = {{0, -1}, {-1, 0}, {0, 1}};

void getInput(){
  cin >> N >> M >> D;
  for(int r=0; r<N; ++r){
    for(int c=0; c<M; ++c){
      cin >> ene[r][c];
    }
  }
}

bool checkCanShoot(int r, int c, int bowC){
  return abs(r - N) + abs(c - bowC) <= D;
}

bool checkBoundary(int r, int c){
  return (r < 0 || c < 0 || r >= N || c >= M);
}

strt findShortest(int c){
  queue<strt> q;
  q.push({N-1, c, 1}); // push archer front
  bool visited[N+1][M+1];
  for(int i=0; i<N; ++i){
    for(int j=0; j<M; ++j){
      visited[i][j] = false;
    }
  }

  while(!q.empty()){
    strt curr = q.front(); q.pop();
    if(visited[curr.r][curr.c]){
      continue;
    }
    visited[curr.r][curr.c] = true;

    if(!checkCanShoot(curr.r, curr.c, c)){
      // can't shoot

      return {0, 0, 0};
    }
    if(ene[curr.r][curr.c] != 0){
      // find shortest
      return curr;
    }

    for(int i=0; i<3; ++i){
      int nr = curr.r + dir[i][0];
      int nc = curr.c + dir[i][1];
      if(checkBoundary(nr, nc)){
        continue;
      }
      q.push({nr, nc, curr.dist + 1});
    }
  }

  return {0, 0, 0};
}

// c1 < c2 < c3
int shoot(int c1, int c2, int c3){
  int kill = 0;

  strt c1Kill = findShortest(c1);
  strt c2Kill = findShortest(c2);
  strt c3Kill = findShortest(c3);

  if(c1Kill.dist != 0){
    if(ene[c1Kill.r][c1Kill.c]){
      ene[c1Kill.r][c1Kill.c] = 0;
      ++kill;
    }
  }
  if(c2Kill.dist != 0){
    if(ene[c2Kill.r][c2Kill.c]){
      ene[c2Kill.r][c2Kill.c] = 0;
      ++kill;
    }
  }
  if(c3Kill.dist != 0){
    if(ene[c3Kill.r][c3Kill.c]){
      ene[c3Kill.r][c3Kill.c] = 0;
      ++kill;
    }
  }

  return kill;
}

void moveEnemy(){
  for(int c=0; c<M; ++c){
    ene[N-1][c] = 0;
  }

  for(int r=N-1; r>0; --r){
    for(int c=0; c<M; ++c){
      ene[r][c] = ene[r-1][c];
    }
  }
  for(int c=0; c<M; ++c){
    ene[0][c] = 0;
  }
}

void copyEne(int _ene[][MAX_N+1]){
  for(int i=0; i<N; ++i){
    for(int j=0; j<M; ++j){
      _ene[i][j] = ene[i][j];
    }
  }
}

void restoreEne(int _ene[][MAX_N+1]){
  for(int i=0; i<N; ++i){
    for(int j=0; j<M; ++j){
      ene[i][j] = _ene[i][j];
    }
  }
}

void solve(){
  getInput();
  int score = 0;
  for(int c1=0; c1<M-2; ++c1){
    for(int c2=c1+1; c2<M-1; ++c2){
      for(int c3=c2+1; c3<M; ++c3){
        int kill = 0;
        int n = N;
        int _ene[MAX_N+1][MAX_N+1];
        copyEne(_ene);

        while(n--){
          kill += shoot(c1, c2, c3);
          moveEnemy();
        }
        score = max(score, kill);
        restoreEne(_ene);
      }
    }
  }

  cout << score;
}

int main(){
  ios::sync_with_stdio(false);
  cin.tie(0);
  solve();

  return 0;
}