백준 17135 캐슬 디펜스 (파이썬)

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

17135번: 캐슬 디펜스

1. 격자판을 입력받으면서 적의 좌표는 enemy에 저장한다

   궁수는 격자판의 맨 아래의 행부터 처리하는 것을 고려한다. 적의 좌표를 enemy의 n-1-i 행에 입력하면 역순이 된다

   그리고 적이 내려올 횟수를 알기 위해서 th에 맨 처음 적이 등장한 행을 th에 저장한다

   th에 변화가 없으면 적이 존재하지 않으므로 0을 출력하고 끝낸다

2. 궁수를 배치할 열을 조합으로 정한다

3. 궁수 3명을 배치했으면 적을 얼마나 죽일 수 있는지 확인한다

   리스트 dead는 죽게 될 적의 좌표를 저장하고 c는 죽은 적의 좌표를 체크해서 중복해서 죽이지 않도록 한다

4. 반복문을 3번 거치는데 처음 반복문은 적이 내려오는 횟수에 대한 반복문이다

   맨 아래의 행 부터 없어지기 때문에 n-th 반복한다

   두번째 반복문은 각 궁수에 대한 반복, 세번째는 사거리에 대한 반복문이다

5. 궁수를 하나씩 불러와서 sx, sy에 좌표를 저장한다

   적이 내려오는 것을 구현하지 않고 궁수가 한 칸씩 올라가는 형태로 구현해서 궁수의 행 좌표가 n-i이 된다

   각 궁수의 케이스마다 최소 거리를 알아야하기 때문에 min_dist를 만든다

6. enemy의 i 행부터 사거리 범위에 해당하는 행까지의 모든 좌표를 확인한다

   c[x][y]가 0이면 아직 죽지 않은 적이므로 거리를 계산하고 사거리 안에 있는지 확인한다

7. min_dist보다 작으면 최소 거리를 갱신하고 dx, dy에 최소 거리가 되는 적의 좌표를 저장한다

   min_dist랑 같으면 가장 왼쪽에 있는 적을 죽이기 위해서 y 좌표를 비교해서 dx, dy를 갱신한다

8. 궁수는 같은 적을 죽일 수도 있기 때문에 dx, dy가 dead 안에 있는지 확인 후 저장한다

9. 궁수 3명이 쏠 적을 확인했으면 죽인 적을 체크한다 (c[x][y] = 1)

10. dead의 길이는 죽인 적의 수가 되므로 이를 비교해서 최대값을 갱신한다

from collections import deque
import sys

input = sys.stdin.readline

def func(cnt, idx):
    global ans
    if cnt == 3:
        dead, flag = [], 0
        c = [[0 for _ in range(m)] for _ in range(n)]
        for i in range(n - th):
            for j in select:
                sx, sy = n - i, j
                min_dist = sys.maxsize
                for k in range(d):
                    if i + k < n:
                        for x, y in enemy[i + k]:
                            if c[x][y] == 0:
                                dist = abs(sx - x) + abs(sy - y)
                                if dist <= d:
                                    flag = 1
                                    if dist < min_dist:
                                        min_dist = dist
                                        dx, dy = x, y
                                    elif dist == min_dist:
                                        if y < dy:
                                            dx, dy = x, y

                if flag and [dx, dy] not in dead:
                    dead.append([dx, dy])

            for x, y in dead:
                c[x][y] = 1

        ans = max(ans, len(dead))
        return

    for i in range(idx, m):
        select.append(i)
        func(cnt + 1, i + 1)
        select.pop()


n, m, d = map(int, input().split())
a, th = [], 16
enemy = [[] for _ in range(n)]
for i in range(n):
    row = list(map(int, input().split()))
    a.append(row)
    if th == 16:
        if 1 in row:
            th = min(th, i)
    for j in range(m):
        if a[i][j] == 1:
            enemy[n - 1 - i].append([i, j])

if th == 16:
    print(0)
    sys.exit()

select = deque()
ans = 0
func(0, 0)
print(ans)