[python] 백준 17135번: 캐슬 디펜스

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

17135번: 캐슬 디펜스

 

분류: 브루트포스/구현 문제

 

규칙

N*M 격자판에 N+1번째 행에 궁수 3명을 배치 할 수 있다.

배치가 끝나면, 격자에 배치된 적들과 궁수 사이 거리가 D 이하일 경우, 가장 가까운거리의 적을

궁수는 화살을 쏴 죽인다. 이 때, 궁수들은 적을 동시에 쏠 수도 있다.

만약 D이하 가장 가까운 적이 여러 명이면 가장 왼쪽의 적을 쏜다.

궁수 3명의 화살쏘기가 1번진행되면, 적들은 N+1의 성을 향해 1칸씩 전진한다.

전진한 적들이 성에 도달하면 화살을 쏠 수 없다.

가장 많은 적을 처치할 때의 그 처치 수를 출력한다.

 

 

헷갈렸던 부분

1. 궁수 배치는 매 턴마다 유동적인게 아니라 게임이 시작되기 전에 정해야 한다.

-> Combination을 활용해 각 경우의 수를 모두 검사함

2. 궁수들은 적을 동시에 쏠 수 있다.

-> 화살에 맞으면 1->0이 되는 것이 아니라, 3명의 궁수가 화살을 다 쏜 경우에 죽이는 걸 처리한다.

3. 궁수들은 가장왼쪽의 적을 죽인다.

-> 단순 for문에서 list sort 를 이용해, 거리 -> 열 순으로 정렬했다. 거리가 최소인 화살쏘기 가능 경우가 여러개일 경우 열이 0에 가까운 곳을 쏜다.

 

코드

from sys import stdin
from itertools import combinations
import copy

died = []

def cal_len(r1, c1, r2, c2):
    return abs(r1 - r2) + abs(c1 - c2)


def can_shoot(chess, row, col, D):
    diclist = []
    global died
    # 거리, col, row 순
    for i in range(row - 1, 0, -1):
        for j in range(M):
            if chess[i][j] == 1:
                length = cal_len(row, col, i, j)
                if length <= D:
                    diclist.append((length, j, i))

    if diclist:
        diclist.sort()
        died.append((diclist[0][2], diclist[0][1]))
        return True

    return False


N, M, D = map(int, stdin.readline().split())

chess = [[0] * (M + 1) for _ in range(N + 1)]

for i in range(1, N + 1):
    chess[i] = list(map(int, stdin.readline().split()))

# archer 위치 조합
archers = [i for i in range(0, M)]
archers_case = list(combinations(archers, 3))

shoot_cnt = 0
result = 0
max_result = 0
# N번
for item in archers_case: # 모든 궁수 조합에 대해
    result = 0
    copy_chess = copy.deepcopy(chess) # 궁수 조합에 따라 다시해야하므로 deep copy 한다.
    for archs_row in range(N + 1, 1, -1): # 가장가까운 행부터
        for archs_col in item: # 각 조합의 궁수 위치에 대해
            if shoot_cnt < 3:  # 3발 보다 적게 쐈다면
                if can_shoot(copy_chess, archs_row, archs_col, D):
                    shoot_cnt += 1

        shoot_cnt = 0
        for enemy in died: # 쏜 적에 대해
            if copy_chess[enemy[0]][enemy[1]] == 1: # 이미 쏘지 않은 적이면
                result += 1 # 죽인 횟수에 더한다
                copy_chess[enemy[0]][enemy[1]] = 0
        died.clear() # 혹시모르니 비운다
    if max_result < result: # 각 궁수 조합의 result 에 대해 최댓값을 찾는다
        max_result = result

print(max_result)