(Python/파이썬) - 백준(BOJ) 17135번 : 캐슬 디펜스

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

17135번: 캐슬 디펜스

---

• 문제 : 

캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 N×M인 격자판으로 나타낼 수 있다. 격자판은 1×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나이다. 격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다.

 

성을 적에게서 지키기 위해 궁수 3명을 배치하려고 한다. 궁수는 성이 있는 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다. 각각의 턴마다 궁수는 적 하나를 공격할 수 있고, 모든 궁수는 동시에 공격한다. 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다. 같은 적이 여러 궁수에게 공격당할 수 있다. 공격받은 적은 게임에서 제외된다. 궁수의 공격이 끝나면, 적이 이동한다. 적은 아래로 한 칸 이동하며, 성이 있는 칸으로 이동한 경우에는 게임에서 제외된다. 모든 적이 격자판에서 제외되면 게임이 끝난다. 

게임 설명에서 보다시피 궁수를 배치한 이후의 게임 진행은 정해져있다. 따라서, 이 게임은 궁수의 위치가 중요하다. 격자판의 상태가 주어졌을 때, 궁수의 공격으로 제거할 수 있는 적의 최대 수를 계산해보자.

 

격자판의 두 위치 (r1, c1), (r2, c2)의 거리는 |r1-r2| + |c1-c2|이다.

 

 

 

---

• 풀이 :

시뮬레이션 문제입니다.

 

문제에서 요구하는 기능들을 적절히 구현하면 됩니다.

 

풀이입니다.

 

1. board를 입력받고, 궁수를 배치할 수 있는 위치인 N번째 행의 3개의 자리만큼 모든 조합의 경우를 따집니다.

(0부터 M-1에서 3개의 수를 선택하는 조합)

 

2. 모든 조합에 대해 궁수의 각 위치에서 사격할 수 있는 적의 위치를 찾습니다. 해당 범위는 좌, 상, 우의 순서로 너비우선 탐색하며 순서는 적을 격추할 때 우선순위가 왼쪽부터이기 때문입니다. 또한, 같은 위치의 적을 사격할 수도 있으므로 set을 사용하여 중복좌표를 제거해줍니다.

 

3. 궁수가 쏠 수 있는 적을 모두 제거한 뒤 (tmp 배열의 좌표들을 0으로 전환) 해당 tmp의 길이만큼 적의 수에서 빼줍니다. 이는 적이 있는 동안 게임을 진행하고 종료 조건으로 적이 0명이 되었을 때를 확인하기 위함입니다.

 

4. 전체 적의 수에서 한 턴의 게임 진행동안 사격한 적의 수 + 성에 도달한 적의 수(del_enemy의 반환값)를 빼줍니다. 

 

5. 모든 적을 한 칸씩 아래로 이동합니다. (move_enemy)

 

6. 궁수 위치의 조합마다 answer를 최댓값으로 갱신합니다.

 

 

 

 

---

• 소스코드 : 

import sys
from itertools import combinations
from collections import deque
import copy
input = sys.stdin.readline

#좌 상 우 순서, 아래는 볼 필요 없음
dx = [0,-1,0]
dy = [-1,0,1]

# 멘해튼거리 계산
def calc_distance(x1,x2,y1,y2):
    return abs(x1-x2) + abs(y1-y2)

# D 거리 안에 있는 사장 가까운 적을 찾음 없다면 False
def find_enemy(col):
    queue = deque()
    queue.append([N-1,col])
    while queue:
        x,y = queue.popleft()
        if calc_distance(N, x, col, y) > D:
            return False
        if board[x][y] == 1:
            return (x,y)
        for i in range(3):
            ax = x + dx[i]
            ay = y + dy[i]
            if 0 <= ax < N and 0 <= ay < M:
                queue.append([ax,ay])

# board에서 모든 적이 한칸 씩 아래로 내려감
def move_enemy():
    for j in range(M):
        for i in range(N-2,-1,-1):
            board[i+1][j] = board[i][j]
    for i in range(M):
        board[0][i] = 0

# 성에 도착한 적을 삭제함
def del_enemy():
    cnt = 0
    for i in range(M):
        if board[N-1][i] == 1:
            cnt += 1
    return cnt

N,M,D = map(int,input().split())
maps = [list(map(int,input().split())) for _ in range(N)]
cnt_enemy = 0 # 처음 적의 수 
answer = 0
for i in range(N):
    for j in range(M):
        if maps[i][j] == 1:
            cnt_enemy += 1

# 0~M-1의 수 중 3개씩 뽑은 모든 조합에 대해 탐색
for comb in combinations(list(range(M)),3):
    del_cnt = 0
    curr_enemy = cnt_enemy
    board = copy.deepcopy(maps)
    # 남아있는 적이 있는 동안 게임 진행
    while curr_enemy > 0:
        tmp = set()
        for i in comb: # 궁수의 위치에서 쏠 수 있는 적을 찾음
            enemy_pos = find_enemy(i)
            if enemy_pos: 
                tmp.add(enemy_pos)
                
        for x,y in tmp: # 궁수가 쏠 수 있는 적을 쏨
            board[x][y] = 0
            
        del_cnt += len(tmp) # 삭제한 적의 수 카운트
        curr_enemy -= len(tmp) # 남은 적의 수 카운트
        curr_enemy -= del_enemy() # 남은 적의 수 카운트
        move_enemy() # 적을 한 칸씩 아래로 내림
    answer = max(answer,del_cnt) # 가장 많은 적을 잡은 경우로 갱신
print(answer)