17135번: 캐슬 디펜스
첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다.
www.acmicpc.net
문제
캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 N×M인 격자판으로 나타낼 수 있다. 격자판은 1×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나이다. 격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다.
성을 적에게서 지키기 위해 궁수 3명을 배치하려고 한다. 궁수는 성이 있는 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다. 각각의 턴마다 궁수는 적 하나를 공격할 수 있고, 모든 궁수는 동시에 공격한다. 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다. 같은 적이 여러 궁수에게 공격당할 수 있다. 공격받은 적은 게임에서 제외된다. 궁수의 공격이 끝나면, 적이 이동한다. 적은 아래로 한 칸 이동하며, 성이 있는 칸으로 이동한 경우에는 게임에서 제외된다. 모든 적이 격자판에서 제외되면 게임이 끝난다.
게임 설명에서 보다시피 궁수를 배치한 이후의 게임 진행은 정해져있다. 따라서, 이 게임은 궁수의 위치가 중요하다. 격자판의 상태가 주어졌을 때, 궁수의 공격으로 제거할 수 있는 적의 최대 수를 계산해보자.
격자판의 두 위치 (r1, c1), (r2, c2)의 거리는 |r1-r2| + |c1-c2|이다.
입력
첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다.
출력
첫째 줄에 궁수의 공격으로 제거할 수 있는 적의 최대 수를 출력한다.
출력
- 3 ≤ N, M ≤ 15
- 1 ≤ D ≤ 10
코드
from itertools import combinations
from copy import deepcopy
n, m, d = map(int, input().split())
board = []
enemies = []
for i in range(n):
lst = list(map(int, input().split()))
for j in range(m):
if lst[j] == 1:
enemies.append([i, j])
# 거리 계산
def get_dist(archer, enemy):
return abs(archer[0]-enemy[0]) + abs(archer[1]-enemy[1])
# 공격할 적 고르기
def attack(archer, enemy_lst):
min_dist = 100
res = None
for i in range(len(enemy_lst)):
dist = get_dist(archer, enemy_lst[i])
if dist <= d and min_dist > dist:
min_dist = dist
res = enemy_lst[i]
return res
def eliminate(archer_position, enemy_lst):
res = 0
while True:
# 종료 조건
if not enemy_lst:
break
# enemy_lst 정렬
enemy_lst.sort(key=lambda x : x[1])
# 궁수 공격
eliminate_enemy = []
for i in range(3):
attacked_enemy = attack(archer_position[i], enemy_lst)
if attacked_enemy:
eliminate_enemy.append(attacked_enemy) # 공격할 적들 저장
for e in eliminate_enemy: # 공격한 적들 enemy_lst 리스트에서 삭제
if e in enemy_lst:
enemy_lst.remove(e)
res += 1
# 적 이동
remove_lst = []
for e in enemy_lst:
e[0] += 1
if e[0] == n: # 성이 있는 칸으로 이동 -> 게임에서 제외
remove_lst.append(e)
# 성으로 이동한 적들 제외
for e in remove_lst:
enemy_lst.remove(e)
return res
ans = 0
for pos in combinations(range(m), 3): # 궁수들 가능한 위치 조합
archers = [[n, i] for i in pos]
enemies_copy = deepcopy(enemies)
ans = max(ans, eliminate(archers, enemies_copy))
print(ans)
'문제풀이 > 구현' 카테고리의 다른 글
[Python/파이썬] 백준 2115번 갤러리 (0) | 2023.07.06 |
---|---|
[Python/파이썬] 백준 17779번 게리맨더링 2 (0) | 2023.06.26 |
[Python/파이썬] 백준 22860번 폴더 정리 (small) (0) | 2023.06.15 |
[Python/파이썬] 백준 2877번 4와 7 (1) | 2023.06.09 |
[Python/파이썬] 백준 20164번 홀수 홀릭 호석 (0) | 2023.05.26 |