[BOJ] 17135. 캐슬 디펜스

문제

캐슬 디펜스 (https://www.acmicpc.net/problem/17135)

풀이

1. 초기접근

• 문제조건 해석

  • 판이 주어지고, 각 턴에 따라 판의 형태가 달라진다.

  • 문제에서 이야기 했 듯, 궁수의 위치가 중요하다. 궁수의 위치에 따라, 진행되는 판의 모양이 달라진다.

    • N, M <= 15 로 주어지고, 궁수의 수도 3명으로 제한된다. 완전탐색으로 풀만하다.
    • 최대 nC3 의 조합의 각 경우에 대해 일일이 탐색해야 한다.

  • 여기서 또 핵심이 되는 조건은 다음이다.

    모든 궁수는 동시에 공격한다. 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다.

    거리가 D이하인 가장 가까운 -> BFS다.
    가장 왼쪽에 있는 -> 방향 순서를 고려해줘야 한다.

  • 같은 적이 여러 궁수에게 공격당할 수 있다는 말은, 각 궁수가 없애고자하는 좌표가 겹칠 수 있다는 말이다.

    • 없앨 좌표를 일괄적을 처리해야 한다.

• 알고리즘

  • 먼저, 각 궁수가 위치할 수 있는 모든 경우를 구한다음, 각 경우를 탐색한다.
    • itertools.combination 을 이용하면 된다.
  • 각 경우에서, 3명의 궁수가 이번 스텝에 없앨 적의 좌표(target) 를 구한다.
    • 좌표의 중복이 허용되므로, set() 을 이용하여 담는다.
  • 없앨 좌표를 일괄적으로 없앤다.
  • 판(board)에서 적들이 한 칸 내려오고, 판에 적이 남았는지 확인한다.
  • 적이 있으면, 다시 위를 반복하고, 없는 경우, 다음 궁수 조합으로 넘어간다.

• 코드

from itertools import combinations
from copy import deepcopy
from collections import deque
dxs = [0, -1, 0]
dys = [-1, 0, 1]

def enemy_move():
    is_empty = True
    for i in range(n-1, 0, -1):
        for j in range(m):
            board[i][j] = board[i-1][j]
            if board[i][j] == '1':
                is_empty = False
    for j in range(m):
        board[0][j] = '0'
    return is_empty

def bfs(x, y):
    q = deque([(x, y)])
    visited = set([(x, y)])
    step = 1

    while q:
        size = len(q)
        for _ in range(size):
            x, y = q.popleft()
            if board[x][y] == '1':
                return (x, y)
            for dx, dy in zip(dxs, dys):
                nx, ny = x + dx, y + dy
                if nx >= 0 and ny >= 0 and ny < m and (nx, ny) not in visited:
                    q.append((nx, ny))
                    visited.add((nx, ny))
        step += 1
        if step > d:
            return None

n, m, d = list(map(int, input().split()))
board_org = [list(input().split()) for _ in range(n)]
max_kill = 0

for locs in combinations(list(range(m)), 3):
    board = deepcopy(board_org)
    kill = 0

    while True:
        targets = set()
        for loc in locs:
            target = bfs(n-1, loc)
            if target is not None:
                targets.add(target)

        for (x, y) in targets:
            board[x][y] = '0'
            kill += 1

        if enemy_move():
            break

    max_kill = max(max_kill, kill)
print(max_kill)