백준 17135 캐슬 디펜스

코드

백준 17135 캐슬디펜스

문제이해

최대 수를 구해야하므로 모든 경우의 수를 확인해야하는 brute force 문제이다. 다음과 같이 순서를 정했다.

1. 궁수를 성에 배치
2. 궁수별로 최단거리 적을 특정
3. 적을 제거
4. 적 한칸 이동 후 맵 끝에 도착한 적 제외

주의해야 할점은 두 가지다. 첫번째로 공격수가 한번 배치되면, 공격수의 위치와 모든 격자판의 사이의 거리는 고정되므로 한번만 계산하면 된다. 적의 이동시마다 새로 계산하게되면 시간이 많이 걸린다.
배치 가능한 공격수의 칸은 $M$ 이고 $N* M$격자판이므로 3중 for-loop로 distance table을 만든다. 3중반복문이라 처음에 망설였으나 입력제한에 $3<= N,M <= 15$를 보니 최대 $15^3$ 이기에 한번 해봤더니 0.00001초도 걸리지 않았다.

두번째로 맵 전체 update할때마다 적의 위치를 찾으면 $M$ iteration마다 $N^2$ 만큼의 연산이 필요하므로 시간복잡도가 $O(M* N^{2})$ 가 된다. 너무 오래 걸리므로 처음 시작할때 적들을 리스트로 관리하면 $O(N^{2})$ 로 처리할 수 있다.

코드

import sys
from itertools import combinations
from copy import deepcopy

N,M,D = map(int, sys.stdin.readline().split())
board = [ list(map(int, sys.stdin.readline().rstrip().split())) for _ in range(N)]

results = combinations( range(M), 3)

counts = []
for m in range(M):
    m_counts = []
    for y in range(N):
        y_lines = [abs(m-x) + abs(N-y) for x in range(M)]
        m_counts.append(y_lines)
    counts.append(m_counts)
    
_enemys = []
for y in range(N):
    for x in range(M):
        if board[y][x] == 1:
            _enemys.append([y,x])


kiiled_list = [0]
for attackers in results:
    killed = 0
    enemys = deepcopy(_enemys)
    while 1:
        if len(enemys) == 0:
            kiiled_list.append(killed)
            break
        
        targets = []
        for a in attackers:
            availabe_target = []
            for e in enemys:
                y,x = e
                d = counts[a][y][x] 
                if d <= D:
                    availabe_target.append((counts[a][y][x], e))

            if len(availabe_target) == 0 :
                continue
                
            min_dist = min([at[0] for at in availabe_target])
            candidate_target = []
            for at in availabe_target:
                if at[0] == min_dist:
                    candidate_target.append(at[1])
        
            if len(candidate_target) == 0:
                continue
            x_cords = [ek[1] for ek in candidate_target ]

            mindix = x_cords.index(min(x_cords))
            targets.append(candidate_target[mindix])       

        for t in targets:
            if t in enemys:
                enemys.remove(t)
                killed += 1

        left_enemy = []
        for e in enemys:
            e[0] += 1
            if e[0] < N:
                left_enemy.append(e) 
        enemys = left_enemy
        
print(max(kiiled_list))