BOJ 17135 캐슬 디펜스(Python 3)

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

 

 

 

일단 먼저 필요한 것이 combinations, deepcopy, deque, Max입니다.

combinations는 궁수가 어디에 위치하고 있는지 모르기 때문에 모든 경우의 수를 구하기 위해 불러왔습니다.

deepcopy는 원본 맵을 복사 하여 각 경우의 수마다 시뮬레이션을 돌려야 하기 때문에 맵의 수정이 필요하므로 불러왔습니다.

deque는 몬스터의 좌표를 저장할 때 쓰입니다.

Max는 공격할 수 있는 적이 여러 명일 때, 가장 왼쪽에 있는 적을 공격하기 위해서 만들었습니다. 이건 설정 안 해도 됩니다.

from itertools import combinations
from copy import deepcopy
from collections import deque
Max = float('inf')

main함수입니다.

여기서 따로 구현한 함수는 NOE와 Attack입니다.

n,m,d = map(int,input().split())
D=[[*map(int,input().split())] for _ in range(n)]
Castle = [i for i in range(m)]
Archer = combinations(Castle,3)
ans = 0
q = deque()
for S in Archer:
    Map = deepcopy(D)
    k = 0
    while 1:
        NOE()
        if len(q) == 0: break
        Attack(q)
        Map = [[0]*m] + Map[:n-1] #아래로 한 칸 이동
    ans = max(ans,k)
print(ans)

 

 

NOE(number of enemies) 함수를 이용하여 적의 좌표를 전부 q에 넣습니다.

만약 적이 없다면 if len(q)==0: break 때문에 while루프에서 빠져나오게 됩니다.

def NOE():
    for i in range(n):
        for j in range(m):
            if Map[i][j]==1:
                q.append((i,j))

 

 

 

Attack함수를 이용하여 각 궁수들이 공격할 좌표를 설정해주고 적을 공격합니다.

def Attack(q):
    global k
    target = [(0,Max),(0,Max),(0,Max)]
    Dist = [Max,Max,Max]
    while q: #공격할 좌표 설정
        x,y = q.popleft()
        for i in range(3):
            z = abs(n-x) + abs(S[i]-y)
            if Dist[i] > z: # 좌표 갱신
                Dist[i] = z
                target[i] = (x,y)
            elif Dist[i] == z and y < target[i][1]: # 같은 거리일 때, 더 왼쪽에 있으면 좌표갱신
                target[i] = (x,y)
    for t,(x,y) in enumerate(target): #공격
        if Map[x][y] == 1:
            if Dist[t] <= d:
                Map[x][y] = 0
                k += 1

 

 

 

 

 

 

 

 

이렇게 해서 완성된 코드입니다.

def NOE():
    for i in range(n):
        for j in range(m):
            if Map[i][j]==1:
                q.append((i,j))
def Attack(q):
    global k
    target = [(0,Max),(0,Max),(0,Max)]
    Dist = [Max,Max,Max]
    while q:
        x,y = q.popleft()
        for i in range(3):
            z = abs(n-x) + abs(S[i]-y)
            if Dist[i] > z:
                Dist[i] = z
                target[i] = (x,y)
            elif Dist[i] == z and y < target[i][1]:
                target[i] = (x,y)
    for t,(x,y) in enumerate(target):
        if Map[x][y] == 1:
            if Dist[t] <= d:
                Map[x][y] = 0
                k += 1
 
from itertools import combinations
from copy import deepcopy
from collections import deque
Max=float('inf')
n,m,d=map(int,input().split())
D=[[*map(int,input().split())] for _ in range(n)]
Castle=[i for i in range(m)]
Archer=combinations(Castle,3)
ans=0
q=deque()
for S in Archer:
    Map=deepcopy(D)
    k=0
    while 1:
        NOE()
        if len(q)==0: break
        Attack(q)
        Map=[[0]*m]+Map[:n-1]
    ans=max(ans,k)
print(ans)