#17135 캐슬 디펜스

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

17135번: 캐슬 디펜스

성을 적에게서 지키기 위해 궁수 3명을 배치하려고 한다. 궁수는 성이 있는 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다. 

각각의 턴마다 궁수는 적 하나를 공격할 수 있고, 모든 궁수는 동시에 공격한다. 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다.

같은 적이 여러 궁수에게 공격당할 수 있다. 공격받은 적은 게임에서 제외된다.

 

궁수의 공격이 끝나면, 적이 이동한다. 적은 아래로 한 칸 이동하며, 성이 있는 칸으로 이동한 경우에는 게임에서 제외된다. 모든 적이 격자판에서 제외되면 게임이 끝난다.

 

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

 

DFS + 구현 문제이다.

궁수의 위치를 dfs를 통해 정해준 후 그떄의 상황에서 문제 조건에 맞게 적을 골라내어 제거할 수 있는 적의 최대 수를 계속해서 갱신하면 된다.

 

실수를 했던부분은 소스코드 28번째 줄 적을 선택하는 함수에서 가장 거리가 가깝고 왼쪽부터 적을 선별해 내야 하는데 for문을 x 다음 y로 돌려서 가장 왼쪽 병사가 선택되지 않았다. -> 코드를 수정하여 y를 바깥쪽 for문으로 놓고 x를 돌렸더니 통과

 

소스코드