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

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

17135번: 캐슬 디펜스

문제 조건에 맞게끔 코딩하면 되는 시뮬레이션 문제. 조건에 맞는 방법을 구현하는 데 삽질을 꽤나 많이 했다.

 

문제의 조건에서 가장 까다로웠던 부분은 '궁사의 적 공격 조건'이었다.

 

1. 거리가 D 이하인 적들 중 가장 가까운 적.

2. 가까운 적이 여러 명이면 '가장 왼쪽'의 적을 공격한다.

3. 여러 궁사가 같은 적을 공격할 수 있다.

 

여기서 '가장 왼쪽'의 적을 선택하는 방법을 구현해보려고

- 궁사의 위치에서 bfs 형태로 가장 가까운 거리에 있는 적을 선택하도록 한다 (실패)

- bfs에서 '다음 탐색지점'활용을 위해 heapq를 써봤다 (실패)

 

하느라 시간을 많이 썼는데, 조금 더 단순하게 생각할 수 있는 문제였다.

 

"가장 왼쪽" == x좌표다.

따라서, 궁사가 공격할 수 있는 거리 기준으로 1차 정렬, 같은 거리라면 x값이 작은 순서대로 정렬하면 된다.