[백준/17135/파이썬] 캐슬 디펜스

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

17135번: 캐슬 디펜스

Problem

• 캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 
• 게임 설명에서 보다시피 궁수를 배치한 이후의 게임 진행은 정해져있다.
• 따라서, 이 게임은 궁수의 위치가 중요하다. 격자판의 상태가 주어졌을 때, 궁수의 공격으로 제거할 수 있는 적의 최대 수를 계산해보자.

조건 

• 게임이 진행되는 곳은 크기가 N×M인 격자판으로 나타낼 수 있다.
• 격자판은 1×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나이다. 격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다.
• 궁수는 성이 있는 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다. 
  1. 각각의 턴마다 궁수는 적 하나를 공격할 수 있고, 모든 궁수는 동시에 공격한다.
  2. 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다. 같은 적이 여러 궁수에게 공격당할 수 있다.
  3. 공격받은 적은 게임에서 제외된다. 궁수의 공격이 끝나면, 적이 이동한다. 적은 아래로 한 칸 이동하며, 성이 있는 칸으로 이동한 경우에는 게임에서 제외된다.
• 모든 적이 격자판에서 제외되면 게임이 끝난다. 
• 격자판의 두 위치 (r1, c1), (r2, c2)의 거리는 |r1-r2| + |c1-c2|이다.

SOL

조건이 굉장히 복잡해보이지만, 크게 순서도를 그리다보면, 어렵지 않은 구현문제이다.

 

1. 궁수를 (N+1)행에 배치를 한다.
   • board를 N+1행으로 늘려도 되지만, M크기만큼의 1차원 배열을 하나 만들어서, 0 = 0,1=1,2=2식으로 만들고, 그 배열에서 3개를 선택하는 모든 경우의 수를 뽑으면 될거같다. 파이썬의 combination은 list의 value를 뽑기 때문에, 이런식으로 구현하면 될듯!
2. 궁수가 적을 공격한다.
   • 궁수가 적을 공격할 때, 조건들이 좀 있다.
   • 거리가 가까운게 최우선, 그게 아니라면, 제일 왼쪽에 있는 친구, 그리고 같은 적이 여러궁수에게 공격당할 수있게 된다.
   • 아처의 현재 자리에서, 적까지의 거리가 가장 가까운 것부터 (D이하) 저장해준다. 이때, 가까운게 여러개가 있다면 제일 왼쪽부터이므로, 우선순위 큐에 적 좌표까지 넣어서 관리를 해주면, 편하다.(min heap이므로, 왼쪽의 정보를 2번째 파라미터로 주면, 자동으로 왼쪽부터 정렬이 된다)
   • 아처는 N+1에 있기 때문에, N부터 배열을 탐색한다.(최소거리)
   • 또, 여러적을 동시에 공격할 수 있기 때문에, 좌표정보를 한번 기록했다가, 기록이 되어있으면 더 세어주지 않기 위해서, monster 방문체크 배열도 있어야할듯하다.
3. 적들이 다가온다.
   • 이건 그냥, 한칸 아래 내려주는걸 구현해주면 된다.
4. 적들이 없으면, 게임이 끝난다.
   • 적들이 없다는 의미는, "1"이 없다는 이야기이다.
   • board에 1이 없으면 끝내자.

import sys
input= sys.stdin.readline
from itertools import combinations
from heapq import heappop,heappush

N,M,D = map(int,input().split())
board=[list(map(int,input().split())) for _ in range(N)]
tmp_board=[]

castle_pos=[x for x in range(M)]
Archers=tuple(combinations(castle_pos,3))
ans=0

def is_end():
    global tmp_board
    flag=False
    for i in range(N):
        for j in range(M):
            if tmp_board[i][j]==1:
                flag=True
                return flag
    return flag

def move_enemy():
    global tmp_board
    tmp_board[-1]=[0 for _ in range(M)]
    for i in range(-1,-N,-1):
        tmp_board[i]=tmp_board[i-1]
    tmp_board[0]=[0 for _ in range(M)]
# 공격을 한다
def atk_enemy(idx):
    global tmp_board
    attacked=[[0 for _ in range(M)]for _ in range(N)]
    attacked_monster=[]
    cnt=0
    for archer_pos in Archers[idx]:
        heapq=[]
        # 가까운것 부터 탐색 
        for i in range(N-1,-1,-1):
            for j in range(M):
                if tmp_board[i][j]==1:
                    dist=abs(N-i)+abs(archer_pos-j)
                    if dist<=D:
                        # mean_heap, j(min)이 가장 위에로 자동 정리.
                        heappush(heapq,[dist,j,i])
        if heapq:
            _,x,y=heappop(heapq)
            attacked_monster.append((y,x))
    #같은 몬스터를 공격할 수도 있으므로, 중복되지 않게 세어준다.
    for y,x in attacked_monster:
        if not attacked[y][x]:
            attacked[y][x] = 1
            cnt+=1
            tmp_board[y][x]=0
    return cnt
def solve(idx):
    cnt=0
    # 적들이 없을 때 까지 반복
    while is_end():
        # 공격을 한다
        cnt+=atk_enemy(idx)
        # 적들을 움직여 준다.
        move_enemy()
    return cnt

for i in range(len(Archers)):
    tmp_board=[[board[i][j] for j in range(M)]for i in range(N)]
    #print(tmp_board)
    cnt= solve(i)
    ans=max(ans,cnt)
print(ans)