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

백준 17135 - 캐슬 디펜스

시간 제한 1초, 메모리 제한 512MB

# 조건

• 캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다.
• 게임이 진행되는 곳은 크기가 N×M인 격자판으로 나타낼 수 있다.
• 격자판은 1×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나이다.
• 격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다.
• 성을 적에게서 지키기 위해 궁수 3명을 배치하려고 한다.
• 궁수는 성이 있는 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다.
• 각각의 턴마다 궁수는 적 하나를 공격할 수 있고, 모든 궁수는 동시에 공격한다.
• 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다.
• 같은 적이 여러 궁수에게 공격당할 수 있다.
• 공격받은 적은 게임에서 제외된다.
• 궁수의 공격이 끝나면, 적이 이동한다.
• 적은 아래로 한 칸 이동하며, 성이 있는 칸으로 이동한 경우에는 게임에서 제외된다.
• 모든 적이 격자판에서 제외되면 게임이 끝난다.
• 게임 설명에서 보다시피 궁수를 배치한 이후의 게임 진행은 정해져있다.
• 따라서, 이 게임은 궁수의 위치가 중요하다.
• 격자판의 상태가 주어졌을 때, 궁수의 공격으로 제거할 수 있는 적의 최대 수를 계산해보자.
• 격자판의 두 위치 (r1, c1), (r2, c2)의 거리는 |r1-r2| + |c1-c2|이다.

입력

• 첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다.
• 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다.
• 0은 빈 칸, 1은 적이 있는 칸이다.

출력

• 첫째 줄에 궁수의 공격으로 제거할 수 있는 적의 최대 수를 출력한다.

# 제한

• 3<=N, M<=15
• 1<=D<=10

# 접근 방법

• 구현, 시뮬레이션 문제이다.
• 따라서 우선 조건을 나눠주면서 아래 키 포인트들을 정리해봤다.
  • 최단 거리의 적을 찾는데 같은 거리라면 가장 왼쪽의 적을 공격
  • 같은 적이 여러 궁수에게 공격 받을 수 있음
  • 적은 공격이 끝난 후 아래로 한 칸 이동 후, 성이라면 제외
• 궁수의 위치를 배치해주기 위하여 itertools의 combination을 사용해주었다.
  • 0~M-1까지의 숫자를 3개씩 뽑아주면 된다.
• 또한 궁수의 배치에 따라 적을 초기화 해주어야 하므로 각 조합을 탐색 시작할 때 origin 배열을 enemy로 깊은 복사해주었다.
• find 함수
  • 각 궁수를 순회하며 모든 적을 탐색한다.
  • 이 때, 가장 좌측 먼저 탐색하도록 enemy를 열을 기준으로 오름 차순 정렬해주었다.
  • 만약 멘허튼 거리가 현재 기록되어있는 min_dist보다 작다면, 해당 적을 갱신하고 위치를 기록해준다.
  • 여러 궁수가 한 적을 공격할 수 있기에 죽이는 적은 set()에 저장해주었다.
  • 만약 죽일 수 있는 적이 있다면 kill_enemy함수를 실행해준다.
• kill_enemy
  • 위치를 순회하며 enemy에서 제거해준다.
  • 또한, 현재 궁수로 죽인 cnt를 +1 해준다.
• move_enemy
  • 궁수의 공격이 끝났으므로 적을 움직여준다.
  • enemy를 순회하며 한 칸 아래가 성 == N이라면 temp에 몇 번째 적인지 기록해준다.
  • 아니라면 enemy값을 갱신해준다.
  • temp가 존재한다면 내림 차순정렬을 하고 해당 되는 인덱스의 적을 제외시켜 준다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  
from itertools import combinations  
from copy import deepcopy  

def find_enemy(loc):  
    global D  
    find = set()  
    for i, j in loc:  
        flag = False  
        min_dist = float('inf')  
        kill = (0, 0)  
        for ei, ej in enemy:  
            dist = abs(i - ei) + abs(j - ej)  
            if dist <= D and dist < min_dist:  
                min_dist = dist  
                kill = (ei, ej)  
                flag = True  
        if flag:  
            find.add(kill)  
    if find:  
        kill_enemy(find)  

def kill_enemy(find):  
    global cnt_kill  
    for fi, fj in find:  
        enemy.remove([fi, fj])  
        cnt_kill += 1  
def move_enemy():  
    temp = []  
    for idx, val in enumerate(enemy):  
        if val[0] + 1 == N:  
            temp.append(idx)  
        else:  
            enemy[idx] = [val[0]+1, val[1]]  
    if temp:  
        temp.sort(reverse=True)  
        for i in temp:  
            enemy.pop(i)  

N, M, D = map(int, input().split())  
arr = [list(map(int, input().split())) for _ in range(N)]  
origin = []  
for i in range(N):  
    for j in range(M):  
        if arr[i][j] == 1:  
            origin.append([i, j])  

result = 0  
for comb in combinations(range(M), 3):  
    enemy = deepcopy(origin)  
    archer = []  
    cnt_kill = 0  
    for c in comb:  
        archer.append([N, c])  
    while enemy:  
        enemy.sort(key=lambda x:x[1])  
        find_enemy(archer)  
        move_enemy()  
    result = max(cnt_kill, result)  
print(result)

• 다만, 삼성 기출인 만큼 itertools를 사용 못한다는 말도 있으니 다음에는 조합을 구현하는 것까지 해야겠다..!