[백준/python] 17135 캐슬 디펜스

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

17135번: 캐슬 디펜스

코드

##17135 캐슬_디펜스
import copy
from itertools import combinations as cm
n, m, d = map(int, input().split())

enemies = []
for _ in range(n):
    row = list(map(int, input().split()))
    enemies.append(row)

distance = -1
if d <= n:
    distance = n-1-d
com = [i for i in range(m)]
combinations = list(cm(com, 3))

answer = 0
for combi in combinations:
    kill = 0
    enemy = copy.deepcopy(enemies)
    done = False
    for _ in range(n):
        shoot = []
        for archer in combi:
            minDis = d
            minJ = m
            minI = n
            for i in range(n-1, distance, -1):
                for j in range(m):
                    if enemy[i][j] == 1 and abs(i-n) + abs(j-archer) <= minDis:
                        if abs(i-n) + abs(j-archer) < minDis:
                            minJ = j
                            minI = i
                            minDis = abs(i-n) + abs(j-archer)
                        else:
                            if j < minJ:
                                minJ = j
                                minI = i
                                minDis = abs(i - n) + abs(j - archer)

            if minJ != m:
                shoot.append((minI, minJ))

        if len(shoot) > 0:
            shoot = list(set(shoot))
            for k in shoot:
                enemy[k[0]][k[1]] = 0
                kill += 1

        enemy = [[0 for _ in range(m)]] + (enemy[0:n-1])
    answer = max(answer, kill)



print(answer)

문제풀이

1. 0 ~ n-1 자리의 궁수 3명의 배치를 구한다(조합)

2. 각 조합별로 문제에서 주어진 조건을 만족시키며 턴을 모두 진행한다.

3.문제 진행중 적을 바로 죽이는 것이 아닌, 모든 경우를 탐색해 가장 짧은 거리, 가장 왼쪽의 조건을 순서대로 만족시키는 ij를 찾은 후 적을 죽인다.

4. 각 조합별로 죽일 수 있는 적의 최대 수를 갱신한 뒤, 반환한다.