백준 / 캐슬 디펜스 / 17135

Question

문제링크
Gold 4

Logic

기본 구조 : combinations, brute
1. 기본적으로 부르투포스 알고리즘을 따르되, 경우의 수 마다 결과가 정해져 있으므로 시뮬레이션 속성을 지닌다.
2. 인덱스의 원활한 비교를 위해 입력된 행렬을 상하 반대로 저장한다.
3. 궁수는 열의 갯수 m에서 mC3의 경우의 수를 가진다.
4. 2를 combinations로 경우의 수를 추출하여 하나씩 결과값을 비교한다.
5. 각 경우의 수 안에서, 한 턴씩 진행한다. 3궁수를 하나씩 접근하면서, 최대거리 D 내에 있는 위치를 탐색하여, 발견된 적을 지정한다.
6. 3궁수를 모두 탐색했으면 지정된 적을 0으로 바꾸고 처치변수를 증가시킨다.
7. 한 턴 탐색을 완료했으면 첫번째 행을 제거한다. 이를 반복한다.
8. 한 경우의 수 탐색이 완료되어 처치한 적 수가 나오면, 최종값과 비교해 최대값을 저장한다.
9. 탐색이 모두 완료되면 최종값을 출력한다.

Code

from sys import stdin
from itertools import combinations
from copy import deepcopy

N,M,D = map(int,stdin.readline().rstrip().split())
enemy = [stdin.readline().rstrip().split() for _ in range(N)]
enemy = enemy[::-1]
answer = 0

for case in list(combinations([i for i in range(M)],3)):
    eliminated = 0
    tmp = deepcopy(enemy)
    nn = N
    while tmp:
        attacked = set()
        for archer in case:
            shot = False
            for d in range(1,D+1):
                i,j = -1,archer-d
                while j < archer+d:
                    if j < archer : i += 1
                    else : i -= 1
                    j += 1
                    if i<0 or i >=nn or j<0 or j>=M : continue
                    else : 
                        if tmp[i][j]=='1' :
                            shot = True
                            break
                if shot : 
                    attacked.add((i,j))
                    break
        for shoted in attacked:
            tmp[shoted[0]][shoted[1]] = '0'
            eliminated += 1
        tmp.pop(0)
        nn -= 1
    answer = max(answer,eliminated)
print(answer)