[Python/파이썬] 백준 17135번 캐슬 디펜스

17135번: 캐슬 디펜스

 

문제

캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 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)