[BaekJoon] 백준 17135번 : 캐슬 디펜스

17135번 : 캐슬 디펜스

주어진 조건대로 순서를 써보자면

궁수가 공격할 위치 선정 → 위치에 있는 적들 죽이기 → 적들 아래로 이동 → 모든 적이 없어질 때까지 반복

궁수가 공격할 위치는 거리가 가장 가까우면서 왼쪽에 있는 적을 공격해야한다.

주어진 필드의 가로, 세로의 최대값이 15 이기 때문에 우선 모든 점을 방문하며 사거리 안에 있는 적들의 위치와 거리 정보를 모두 담는다.

그리고 거리를 기준으로 오름차순 정렬을 먼저 하고 column 값을 기준으로 오름차순 정렬을 한 번더 한다.

그렇게 되면 거리가 가장 가까우면서 맨 왼쪽에 있는 적의 위치를 알 수 있다.

공격할 위치를 모두 정했으면 적들을 다 죽인다.

적들을 아래로 이동하는 경우는 필드를 deque 로 만든 뒤 빈 줄을 맨 왼쪽에 넣어주고 맨 오른쪽은 지우면 된다.

이렇게 모든 적이 없어질 때 까지 반복하면 잡을 수 있는 적의 수를 구할 수 있다.

하지만 최대로 잡을 수 있는 적을 구해야하기 때문에 궁수가 위치할 수 있는 모든 경우에 대해 검사를 해주면 된다.

---

import sys
from collections import deque
from copy import deepcopy
from itertools import combinations


# 적들이 아래로 이동하는 함수
def move_enemy(field):
    row = [0] * M
    field.appendleft(row)
    field.pop()


# 궁수가 쏠 위치를 정하는 함수
def choice_attack_location(field, arrow):
    all_attack_location = list()
    for i in range(N):
        for j in range(M):
            distance = abs(arrow[0] - i) + abs(arrow[1] - j)
            if distance <= D and field[i][j] == 1:
                all_attack_location.append((distance, i, j))

    all_attack_location.sort(key=lambda x: (x[0], x[2]))
    if all_attack_location:
        return True, all_attack_location[0]
    else:
        return False, None


# 세 명의 궁수가 쏠 위치를 저장하는 함수
def init_attack_location(field, arrows):
    attack_location = list()
    for arrow in arrows:
        arrow_attack_loc_check = choice_attack_location(field, arrow)
        if arrow_attack_loc_check[0]:
            attack_location.append(arrow_attack_loc_check[1])

    if attack_location:
        return set(attack_location)

    return attack_location


def defense(field, arrows):
    kill = 0

    # 적이 없어질 때 까지 반복
    while sum(sum(field, [])) != 0:

        # 세 명의 궁수가 쏠 위치 저장
        attack_location = init_attack_location(field, arrows)

        # 공격
        for attack in attack_location:
            if field[attack[1]][attack[2]] == 1:
                kill += 1
                field[attack[1]][attack[2]] = 0

        # 적들 아래로 이동
        move_enemy(field)

    return kill


def solution():
    answer = -float('inf')
    arrows = [(N, i) for i in range(M)]

    for value in combinations(arrows, 3):
        answer = max(answer, defense(deepcopy(field), value))

    return answer


if __name__ == "__main__":
    N, M, D = map(int, input().split())
    field = deque([list(map(int, sys.stdin.readline().rsplit())) for _ in range(N)])

    print(solution())