백준 17135 캐슬 디펜스 파이썬

문제에 주어진 조건들만 잘 활용하면 쉽게 풀 수 있는 문제였다.

자세한 코드 설명은 코드와 함께 하겠습니다.

from itertools import combinations
import copy
import heapq #개인적으로 heap사용 덕분에 쉽게 푼거 같다.

def bfs(t,sk):#거리에 맞는거 찾기(t = 조합중에 하나,sk=s배열을 deepcopy한것)
    hpq = []
    for i in range(n):
        for j in range(m):
            if sk[i][j]==1:#만약에 병사가 있다면
                for u in t:#각 사수들로부터 거리를 구해줌
                    if abs(n-i)+abs(u-j)<=d:#사정거리 안이면 heap에 저장
                        heapq.heappush(hpq,(abs(n-i)+abs(u-j),j,i,u))
                        #(사정거리,j,i,사수위치)인 이유 문제 조건이 사정거리가 짧은 곳을 우선으로 하고 
                        #거리가 같을때는 왼쪽을 먼저 쏘라고 했어서 사수위치는 같은 병사를 쏠 수 있기때문.
    return hpq

def shot(hpq,s,cont):#죽이기
    
    vist = [False]*(m)#사수의 발사 여부
    while hpq:
        q,j,i,t = heapq.heappop(hpq)
        if not vist[t]:#사수가 안 쐈으면 쏜다.
            vist[t]=True#쐈으니 True
            if s[i][j]==1:만약에 1이면 아직 병사가 살아있다는 것이니
                cont+=1#처치 병사 +1
            s[i][j]=0# 이병사는 죽을 수 밖에 없으므로 0으로 바꿔줌
    return cont#죽인 병사의 수 return
    
def move(s):#움직이기
    for i in range(n-1,-1,-1):#한칸씩 아래로 내려준다.
        for j in range(m):
            s[i][j] = s[i-1][j]
def main(i):#코드의 간결화를 위해서 main함수를 만들어줌.
    global maxs
    cont =0
    sk = copy.deepcopy(s)
    for _ in range(n):#병사가 0행에 있을 수 있으니 n번 내려주면 남아있는 병사는 없음.
        h = bfs(i,sk)
        cont = shot(h,sk,cont)
        move(sk)
    maxs = max(cont,maxs)#최댓값 갱신
    
n,m,d =map(int,input().split())
s =[list(map(int,input().split())) for i in range(n)]
s.append([0]*m)#move할때 위에 0행을 0으로 채우기 위해 추가해줌
cos = list(combinations([i for i in range(m)],3))#사수를 배치할 수 있는 모든 경우의 수
maxs = -1 
for i in cos:
    main(i)#main(i)함수 작동해줌으로써 사수의 위치가 i 일때 죽인 병사의 값을 알려줌
print(maxs)