이번 문제는 함수로 따로 모듈화하여 해결하였다.

궁수가 최대한 많은 적을 죽이기 위해서는 성과 같은 y축에 있어야 한다(적을 최대한 오래 봐야 하기 때문). get_arrows함수는 3명의 궁수의 x축의 모든 경우를 구해야하기 때문에 이를 백트레킹을 통해 구현하였다.

그리고 적이 한칸씩 성쪽으로 이동하는 동작을 move_enemy() 함수로 구현하였다. 임시 리스트에 [0 * m]을 넣고 tmp_grid의 리스트들을 넣는 방식으로 하여 리스트가 한칸씩 밑으로 밀리도록 하였다.

조건에 맞도록 가장 가깝고 가장 왼쪽에 있는 적을 찾는 함수로 find_attackable를 구현하였다. BFS를 통해 탐색하며 거리가 d보다 작고 1일 경우에 결과 리스트에 담고, 결과 리스트를 정렬하여 가장 앞쪽의 좌표와 거리를 반환하도록하였다. 이렇게 반환된 값들은 set()에 담아 중복을 없애고, set()을 순회하며 적을 제거하고 결과변수를 카운팅하도록 하였다.

Code

import copy
from collections import deque
n, m, d = map(int, input().split())
grid = [list(map(int, input().split())) for _ in range(n)]
dy, dx = [0, 1, 0, -1], [1, 0, -1, 0]
answer = 0
arrows = []
def get_arrows(cur, arrow):
    if cur == m:
        if len(arrow) == 3:
            arrows.append(arrow)
        return
    if len(arrow) > 3:
        return
    get_arrows(cur+1, arrow+[(n, cur)])
    get_arrows(cur+1, arrow)
def move_enemy():
    global tmp_grid
    result = [[0 for _ in range(m)]]
    for i in range(n-1):
        result.append(tmp_grid[i])
    tmp_grid = copy.deepcopy(result)
def find_attackable(arrow, grid):
    y, x = arrow
    q = deque()
    q.append((y, x, 1))
    visited = [[False for _ in range(m)] for _ in range(n)]
    results = []
    while q:
        y, x, dist = q.popleft()
        if dist > d:
            continue
        for i in range(4):
            ny, nx = y+dy[i], x+dx[i]
            if 0 <= ny < n and 0 <= nx < m and not visited[ny][nx]:
                visited[ny][nx] = True
                q.append((ny, nx, dist+1))
                if grid[ny][nx] == 1:
                    results.append((ny, nx, dist+1))
    if not results:
        return (-1, -1)
    results.sort(key=lambda x:(x[2], x[1], x[0]))
    return (results[0][0], results[0][1])
get_arrows(0, [])
for i in range(len(arrows)):
    tmp_ans = 0
    tmp_grid = copy.deepcopy(grid)
    while tmp_grid != [[0 for _ in range(m)] for _ in range(n)]:
        rmv = set()
        for j in range(3):
            rmv.add(find_attackable(arrows[i][j], tmp_grid))
        for ry, rx in rmv:
            if (ry, rx) == (-1, -1):
                continue
            tmp_grid[ry][rx] = 0
            tmp_ans += 1
        move_enemy()
    answer = max(answer, tmp_ans)
print(answer)