백준 17135. 캐슬 디펜스

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

17135번: 캐슬 디펜스

 

궁수 세명이 있을수 있는 모든 위치에 대하여 제거할 수 있는 적들의 최댓값을 구하는 문제다. 

궁수 들의 위치는 permutation 함수로 모든 경우를 구해줬다.

 

그리고 각 궁수들이 격퇴하는 적이 누구인가를 판단해야 하는데, 문제의 조건이 D 이내의 가장 가까운 적들, 가장 가까운 적들이 여러명이면 가장 왼쪽에 있는 적을 격퇴한다고 했다.

bfs를 이용해 왼쪽, 위, 오른쪽 순서대로 칸을 탐색하고 적을 만나면 bfs를 빠져나오도록 했다.

이렇게 하면 자연스럽게 가장 가깝고 가장 왼쪽에 있는 적을 격퇴하게 된다.

 

주의할 점은 세명의 궁수들은 동시에 화살을 쏘기 때문에 한명의 궁수가 격퇴했다고 1을 0으로 만들어버리면 안된다.

나는 격퇴했을시 1을 2로 만들어서, 격퇴한 적이 1이었다면 격퇴한 적의수를 증가시키고, 2였다면 증가시키지 않도록 했다. 

 

마지막으로는 화살을 일제히 쏜 후 적들이 한칸 아래로 이동해야 한다.

어처피 N번째 행에 있는 적들은 모두 성으로 이동할테니 N번째 행은 다 0으로 만들어주면 된다.

그리고 적들은 아래로 이동하기 때문에 N-1행부터 0행까지 차례로 한칸씩 아래로 이동시켜 주면된다. 

0행 부터 N-1행까지 이동시킬 경우 데이터 손실이 일어난다.