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

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

 

 

이 문제는 2단계로 진행된다. 첫 번째는 궁수가 적을 공격하는 단계, 두 번째는 적이 한 칸 이동하는 단계다.

첫 번째로 궁수가 적을 공격하는 단계는 궁수를 배치할 수 있는 경우를 combinations를 사용해 구하고, 각 comb 케이스별로 궁수의 위치에서 bfs를 통해 거리가 d이하고, 가장 왼쪽에 있는 적의 위치를 저장한다. 저장한 적의 위치는 제거되므로 0으로 바꾼다.

두 번째 단계는 적이 앞으로 1칸 이동하고, 성벽에 닿으면 제거되는 단계이다. 인덱스를 1씩 늘리면 된다.

이 두 단계를 모든 적이 없을 때까지 반복하면 된다.

 

import sys
from itertools import combinations
from collections import deque
input = sys.stdin.readline


n, m, d = list(map(int, input().split()))
board = [list(map(int,input().split())) for _ in range(n)]

dx = [0,-1,0]
dy = [-1,0,1]

enemy = []
for i in range(n):
    for j in range(m):
        if board[i][j] == 1:
            enemy.append([i,j])

# 궁수가 적을 공격하는 단계
def attack(comb,enemy):
    removeEnemy = []

    for c in comb:
        r = n
        q = deque([[r,c]])
        visited = [[0]*m for _ in range(n)]

        # 각 궁수의 위치에서 bfs를 통해 제거될 적의 위치를 저장
        while q:
            cx,cy = q.popleft()

            if abs(cx-r)+abs(cy-c) > d:
                break

            if [cx,cy] in enemy:
                removeEnemy.append([cx,cy])
                break

            for i in range(3):
                nx,ny = cx+dx[i],cy+dy[i]
                if 0<=nx<n and 0<=ny<m:
                    if visited[nx][ny] == 0:
                        visited[nx][ny] = 1
                        q.append([nx,ny])

    # 적을 동시에 제거
    cnt = 0
    for r,c in removeEnemy:
        if [r,c] in enemy:
            enemy.remove([r,c])
            cnt += 1
                 
    return cnt

# 적이 이동하는 단계
def move(enemy):
    for i in range(len(enemy)):
        enemy[i][0] += 1
    temp = enemy[:]
    for r,c in temp:
        if r>=n:
            enemy.remove([r,c])


def solve(comb,enemy):
    result = 0
    while enemy:
        result += attack(comb,enemy)
        move(enemy)
    return result

answer = -1

# 모든 경우의 수를 탐색
for comb in combinations(range(m),3):
    e = [row[:] for row in enemy]
    answer = max(answer, solve(comb,e))

print(answer)