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

난이도 : GOLD III

문제링크 : https://www.acmicpc.net/problem/17135

문제해결 아이디어

문제의 조건을 요약 하면 다음과 같다.

궁수를 3명 배치
궁수는 거리가 D 이하인 적 중에서 가장 가까운 적 공격
만약 거리가 같으면 왼쪽부터, 중복가능
화살 쏜 이후 적 한칸씩 이동
적이 castle에서 사라지면 게임 종료텍스트
제거 할수 있는 적의 최댓값을 구해라

사실 그냥 구현문제라서 아이디어가 필요없다..

궁수를 3명 배치 => 조건을 보고 조합라이브러리를 통해 3명이 배치될수 있는 모든 경우의 수중 최대값을 답으로 제출해야 겠다고 생각했다.

궁수는 거리가 D 이하인 적 중에서 가장 가까운 적 공격 => 궁수와의 거리가 D 이하이며 castle[x][y] == 1 인경우에 배열에 [거리, x, y] 를 저장한다. 저장한 배열을 거리를 기준으로 오름차순, y좌표 기준으로 오름차순 으로 정렬하고 제거한다 (가장 가까운적부터 제거, 거리가 같으면 왼쪽부터제거)

소스코드

import sys
from itertools import combinations
import copy

input = sys.stdin.readline

n, m, d = map(int, input().split())
_map = []
ans = 0

for _ in range(n):
    _map.append(list(map(int, input().split())))

def find(combi, castle): # 각 궁수들의 위치 마다 사정거리 안의 적들의 좌표 
    arr = []
    for c in combi:
        enemy = [] 
        for i in range(n):
            for j in range(m):
                if castle[i][j] == 1 and abs(n - i) + abs(c - j) <= d:
                    enemy.append((abs(n - i) + abs(c - j), i, j)) # 거리, x, y

        arr.append(enemy)
    return arr


def attack(arr, castle):  # 적 제거
    removed = set() # 적이 중복되서 제거 될수도 있으므로
    for candi in arr:
        if not candi:
            continue
        candi.sort(key=lambda x: (x[0], x[2]))  # 거리가 짧은순, y 좌표가 작은순
        removed.add((candi[0][1], candi[0][2]))
        castle[candi[0][1]][candi[0][2]] = 0
    return len(removed)


def move_castle(castle):
    for i in range(n - 1, 0, -1):
        castle[i] = castle[i - 1]

    castle[0] = [0] * m


def check_empty(castle):
    for i in range(n):
        for j in range(m):
            if castle[i][j] == 1:
                return False
    return True


for c in combinations([i for i in range(m)], 3):
    castle = copy.deepcopy(_map)
    cnt = 0
    while not check_empty(castle):
        arr = find(c, castle)
        cnt += attack(arr, castle)
        move_castle(castle)

    ans = max(ans, cnt)

print(ans)