[백준] 17135 캐슬 디펜스

---

N*M의 격자판에서 3명의 궁수를 위치시켜 잡을 수 있는 적의 최대를 구하는 문제이다.

 

궁수가 적을 잡는 경우

1. 궁수는 D 거리 이하에 있는 적만을 잡을 수 있다.

2. 궁수는 가장 가까운 적을 죽인다.

3. 그러한 적이 여러명 존재할 경우 가장 왼쪽에 위치한 적을 죽인다.

4. 같은 적을 죽일 수 있다.

 

궁수 배치하기

가능한 모든 궁수들의 배치를 구해야 하기 때문에 itertools 모듈의 combinations를 사용한다.

 

죽일 적 찾기 & 적 죽이기

D 거리 이하에 위치하고 가장 가까운 적을 찾기 위해서 BFS를 활용한다. 이때 파이썬의 heapq 모듈을 사용한다.

궁수와 적간의 거리, 궁수의 위치를 큐에 저장한다. 단 거리가 D를 초과하면 잡을 수 있는 적이 존재하지 않기 때문에 (-1, -1)을 반환한다.

 

heapq 모듈은 원소의 순서에 따라 우선순위를 부여하기 때문에 (거리, Column, Row) 순으로 데이터를 삽입한다.

 

같은 적을 죽일 수 있기 때문에 각 궁수가 적을 찾자 마자 죽이는 것이 아니라 적을 모두 찾은 후 죽인다.

 

적 이동

적을 아래로 이동 시키기 위해 배열 전체를 라인 스왑 하는 것이 아니라 궁수의 위치를 한 칸 위로올린다.

 

 

Python