완전탐색, BFS, 구현 - 17135번: 캐슬 디펜스

• 리스트에 튜플 형태로 저장 시 각 값의 저장 순서 주의하기
• 여러 경우의 수에 대해 시뮬레이션하는 경우 매 턴마다 입력받은 맵을 deepcopy해서 써야 함
• while문 종료 조건에 들어간 변수 매번 갱신 주의

from itertools import combinations
from collections import deque


# 1) m만큼의 자리에 궁수 3명을 성에 배치할 수 있는 경우의 수(0 ~ m-1 의 숫자중 3개 고르는 모든 조합 구하기)
# 2) 궁수와 D거리 이하인 적 중 가장 가까운, 가장 왼쪽에 있는 적 공격(여러 궁수가 하나의 적 공격 가능)
# 3) 공격된 적은 죽음
# 4) 남은 적 아래로 한칸씩 모두 이동
# 5) 성에 도착한 적은 제외
# 6) 위를 반복하다 모든 적이 제외되면 종료


line = list(map(int, input().split()))


n, m, d = line[0], line[1], line[2]

maps = []


for i in range(n):
    line = list(map(int, input().split()))
    maps.append(line)


killer_area = list(range(0, m))
area_combi = list(combinations(killer_area, 3))


dx = [-1, 0, 0]
dy = [0, -1, 1]


def kill_enemies(killer_list, copy_maps):

    enemy_list = []
    kill_cnt = 0

    for k in killer_list:  # 킬러 위치: [n][k]

        q = deque()
        visited = [[False] * m for _ in range(n)]

        q.append((n, k))
        # visited[n-1][k] = True

        candidates = []

        while q:
            x, y = q.popleft()

            for i in range(3):
                nx, ny = x + dx[i], y + dy[i]

                dist = abs(nx - n) + abs(ny - k)

                if 0 <= nx < n and 0 <= ny < m and not visited[nx][ny]:
                    if copy_maps[nx][ny] == 1 and dist <= d:
                        candidates.append((dist, nx, ny))
                    elif copy_maps[nx][ny] == 0 and dist <= d:
                        q.append((nx, ny))
                    visited[nx][ny] = True

        if len(candidates) > 1:
            candidates.sort(key=lambda x: (x[0], x[2]))
            enemy_list.append(candidates[0])
        elif len(candidates) == 1:
            enemy_list.append(candidates[0])

    # 각 궁수가 죽일 적 리스트 처리
    for dist, x, y in enemy_list:  # 저장 순서 주의!!!
        if copy_maps[x][y] == 1:
            copy_maps[x][y] = 0
            kill_cnt += 1

    return kill_cnt


def move_enemies(copy_maps):

    # 적 아래로 한칸씩 이동
    for i in range(n - 1, -1, -1):
        for j in range(0, m):
            if copy_maps[i][j] == 1:  # 적이 있는 경우

                if i == n - 1:
                    copy_maps[i][j] = 0
                else:
                    copy_maps[i][j] = 0
                    copy_maps[i + 1][j] = 1

    return


max_kill_cnt = -1

for i in range(0, len(area_combi)):
    killer_list = area_combi[i]

    # 매 턴마다 입력받은 맵 복사해서 써야함 주의
    copy_maps = [row[:] for row in maps]

    turn_cnt = 0  # 이번 조합에 죽인 적 수

    enemy_sum = 0
    for j in range(0, n):
        enemy_sum += sum(copy_maps[j])

    # 맵에 적이 없을 때까지 반복
    while enemy_sum > 0:

        kill_cnt = kill_enemies(killer_list, copy_maps)
        turn_cnt += kill_cnt  # 누적
        move_enemies(copy_maps)

        # 매 공격 턴 끝난 후에 맵에 남은 적 다시 계산해주기!!
        enemy_sum = 0
        for j in range(0, n):
            enemy_sum += sum(copy_maps[j])

    # 게임 종료되면 최댓값 갱신
    max_kill_cnt = max(max_kill_cnt, turn_cnt)


print(max_kill_cnt)