백준 구현 대비 캐슬디펜스

접근

도식화 과정은 다음과 같다.
궁수 세명 배치 -> 궁수공격 -> 적이동

위 문제에서 다음 부분을 간과하여 시간을 오래 잡아먹었다.

궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다. 같은 적이 여러 궁수에게 공격당할 수 있다.

처음에는 안일하게 위 부분을 다음과 같이 코드를 작성하였다.

if abs(co[0]-i)+abs(co[1]-j)<maxdist:
	maxdist=abs(co[0]-i)+abs(co[1]-j)
    maxenem=[i,j]

위 코드는 일반적인 반복문처럼 맨 왼쪽에서 부터 그래프의 원소르 탐색하여 이전의 최솟값보다 작은 값을 발견했을때 가장 거리가 가까운 적을 찾아줄 수 있지만. 이전의 적과 거리가 같으면서 왼쪽에 있는 적은 판단해주지 못한다. 즉 이전과 거리가 같은 경우에도 다시 계산해주도록 코드를 바꾸어 짜야 한다. 앞으로 이렇게 같은 값들 사이의 우선순위 또한 판단해주어야 하는 문제는 조건문을 둘 다 작성하도록 하자/.

          if abs(co[0]-i)+abs(co[1]-j)<maxdist:
              maxdist=abs(co[0]-i)+abs(co[1]-j)
              maxenem=[i,j]
            elif abs(co[0]-i)+abs(co[1]-j)==maxdist:    # 같을경우도 따로 count 해주어야 한다.
              if j<maxenem[1]:
                maxenem=[i,j]

전체코드

from itertools import combinations
N,M,D=map(int, input().split())
graph=[]
archer=[]
numofenemy=0
maxkilled=0
for i in range(N):
  graph.append(list(map(int, input().split())))

for i in range(N):
  for j in range(M):
    if graph[i][j]==1:
      numofenemy+=1

for i in range(M):
  archer.append([N,i])

archercomb=list(combinations(archer,3))   

for comb in archercomb:                 
  tempgraph=[ item[:] for item in graph ] 
  killed=0
  tempenem=numofenemy

  while tempenem>0:
    enemlist=[]
    for co in comb:              
      maxdist=1e9
      maxenem=None
      for i in range(N):       
        for j in range(M):     
          if tempgraph[i][j]==1 and abs(co[0]-i)+abs(co[1]-j)<=D:
            if abs(co[0]-i)+abs(co[1]-j)<maxdist:
              maxdist=abs(co[0]-i)+abs(co[1]-j)
              maxenem=[i,j]
            elif abs(co[0]-i)+abs(co[1]-j)==maxdist:    # 같을경우도 따로 count 해주어야 한다.
              if j<maxenem[1]:
                maxenem=[i,j]
      if maxenem:
        enemlist.append(maxenem)

    for en in enemlist:        
      if tempgraph[en[0]][en[1]]==1:
        tempenem-=1
        killed+=1
        tempgraph[en[0]][en[1]]=0
    # 여기까지가 죽이는 과정

    #이제 움직여
    tempenem-=tempgraph[-1].count(1)
    newtempgraph=[[0 for i in range(M)]]
    for i in range(N-1):
      newtempgraph.append(tempgraph[i])
    tempgraph=newtempgraph
  maxkilled=max(maxkilled,killed)

print(maxkilled)