본문 바로가기

■ 알고리즘 문제 풀이/BOJ

[BOJ] 백준 17135. 캐슬 디펜스

▶문제설명

[BOJ] 백준 17135. 캐슬 디펜스

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



▶Hint


BFS & 브루트 포스 & 시뮬레이션 문제이다.


궁수 3명이 만들 수 있는 모든 배치를 고려해야하고,

사정거리에 들어있는 적을 탐색하는 과정에 BFS를 수행하며,

모든 적군이 성으로 들어오기까지 몇 명의 적을 사살할 수 있는지 시뮬레이션 해봐야 답을 도출할 수 있다.


1. 궁수 3명을 배치한다.

2. 궁수들이 적군들 중 타겟을 정한다.

(사정 거리 내에 있는 적군들 중 거리가 짧은 적군을 우선하고, 

거리가 같은 적군이 여러 명일 경우 가장 왼쪽에 있는 적군을 타겟으로 한다.)

3. 타겟을 제거한다.

4. 모든 적군이 한 칸 앞으로 몰려온다.

5. 2~4 과정을 모든 적군이 성으로 들어올 때까지 반복해서 수행한다.

6. 1~5 과정을 궁수 3명을 배치할 수 있는 모든 경우에 대해서 수행한다.



▶Solution