[백준 17135] 캐슬 디펜스(python)

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

17135번: 캐슬 디펜스

캐슬 디펜스 문제

궁수 3명을 배치해서 적을 최대 몇까지 제거할 수 있는지 세는 문제,

BFS와 완전 탐색을 이용해서 해결 할 수 있었다.

📌 문제 접근 포인트

1. 조건이 많은 문제이므로, 각각 구현해야하는 조건을 먼저 생각하자.
2. 적이 앞으로 전진하는 형태로 구현해도 가능하지만, 궁수가 앞으로 이동하는 형태로 구성하는게 조금 더 쉽게 가능하다.
3. 반복적으로 탐색을 진행해야하니, 판을 복사해서 사용하는 것을 반복하고, 아처 3명을 뽑는 각각의 조합을 이용하도록 함수를 구성해주자.
4. 적을 제거할 때, 궁수가 동시에 공격을 진행하므로 마지막에 모아서 처리를 해주고, 각각 이동할 때마다 거리가 1씩 증가하므로, BFS를 이용해서 찾아주면서 거리를 +1씩 해주자. 
5. 요구조건에 맞게 각각 구현해주면 구현 성공!

⚙ 내가 푼 정답 코드

# 조건 1. 격자 판 N*M, 각 칸당 적의 최대 수 1
# 조건 2. 궁수 3명 배치. 성이 있는 칸에 배치할 수 있고, 한칸에 최대 수 1
# 조건 3. 턴마다 궁수는 적하나 공격 가능, 모든 궁수 동시 공격
# 조건 4. 공격 거리 D이하, 여럿이면 왼쪽부터 공격하고 공격 받으면 적은 판에서 제거
# 조건 5. 공격이 끝나면 1칸씩 전진, 아래로 1칸 이동하고 성이 있는 칸으로 이동하면 판에서 제거 -> 적이 아니라 궁수가 올라가도 동일

def hunt(archor):
    boards = deepcopy(board) # 보드 복사 
    visited = [[0] * M for _ in range(N)] # 방문처리
    cnt = 0
    for i in range(N-1, -1, -1): # 한칸씩 전진(적이 아닌 궁수가 전진) (조건5)
        die = []
        for m in archor: # 뽑은 궁수 자리에 대해 (조건2)
            queue = deque([[i, m, 1]])
            while queue:
                y, x, d = queue.popleft()
                if boards[y][x] :
                    die.append([y, x])
                    if not visited[y][x]:
                        visited[y][x] = 1
                        cnt += 1 # 죽였으니 점수 증가
                    break

                if d < D: # 사정거리보다 짧으면 (조건4)
                    for dx, dy in move:
                        nx, ny = x + dx, y + dy
                        if 0 <= ny < N and 0 <= nx < M:
                            queue.append([ny, nx, d+1]) # 거리 증가

        for y, x in die:# (조건3) 모든 궁수가 동시에 공격하니 마지막에 처리
            boards[y][x] = 0

    return cnt

import sys
from copy import deepcopy
from collections import deque
from itertools import combinations
N, M, D = map(int, sys.stdin.readline().split())
board = [list(map(int, sys.stdin.readline().split())) for _ in range(N)] # (조건 1)
move = [[-1,0],[0,-1],[1,0]]
result = 0
for archor in combinations([i for i in range(M)], 3): #(조건2)
    result = max(result, hunt(archor))
print(result)