[백준] 17135번 - 캐슬 디펜스 (파이썬)

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

# 캐슬 디펜스
import copy
import sys
input = sys.stdin.readline
MAX = sys.maxsize

N, M, D = map(int, input().split())
arr = []
enemy = []
for i in range(N):
    arr.append(list(map(int, input().split())))
    for j in range(M):
        if arr[i][j] == 1:
            enemy.append([i, j])
enemy.sort(key=lambda x: x[1]
arch = []
target = []
result = 0


def archPositon(count, k):
    if count == 3:
        temp = copy.deepcopy(arr)
        tenemy = copy.deepcopy(enemy)
        start(temp, tenemy)
    for i in range(k, M):
        arch.append((N, i))
        archPositon(count+1, i+1)
        arch.pop()


def start(arr, enemy):
    global result
    temp = 0
    for _ in range(N):
        getTarget(arr, enemy)
        temp += killTarget(arr)
        move(arr, enemy)
    result = max(result, temp)


def getTarget(arr, enemy):
    for x, y in arch:
        temp = MAX
        target_x = -1
        target_y = -1
        for a, b in enemy:
            if arr[a][b] == 1:
                len = abs(x-a)+abs(y-b)
                if temp > len and len <= D:
                    target_x = a
                    target_y = b
                    temp = len
        if target_x != -1 and target_y != -1:
            target.append((target_x, target_y))


def killTarget(arr):
    temp = 0
    while target:
        x, y = target.pop()
        if arr[x][y] == 1:
            temp += 1
            arr[x][y] = 0
    return temp


def move(arr, enemy):
    zero = []
    one = []
    for k in range(len(enemy)):
        x = enemy[k][0]
        y = enemy[k][1]
        if arr[x][y] == 1:
            zero.append((x, y))
            if x + 1 < N:
                enemy[k][0] += 1
                one.append((x+1, y))
    while zero:
        x, y = zero.pop()
        arr[x][y] = 0
    while one:
        x, y = one.pop()
        arr[x][y] = 1


archPositon(0, 0)
print(result)

 

백트랙킹

1. 입력을 받으면서 1이면 enemy리스트에 append

2. enemy를 j의 값을 우선시해서 정렬 (같은 거리에 있는 적일 경우 왼쪽먼저 처치)

3. archPosition : 궁수의 위치를 배치 (3명)

    - start : 디펜스게임 시작 N길이만큼 반복

       - getTarget : 죽일 타겟을 정함 가장 가까운 거리에 있는 적의 좌표를 target리스트에 append

       - killTarget : target리스트의 좌표 x,y를 이용해서 arr[x][y] = 0, 죽인적 더하기

       - move : 살아있는 적들을 아래로 한칸 씩 이동