백준: 17135 캐슬 디펜스

문제

17135번: 캐슬 디펜스

 

문제 풀이

 문제에서 격자판과 궁수의 공격 거리 제한 D가 주어 질 때 제거할 수 있는 적의 최대 수를 출력하는 문제이다. 궁수는 3명을 배치할 수 있으며, 배치 가능한 범위는 열의 범위인 M까지 이다.

 

 궁수의 경우 3명만 배치 가능하므로 각 좌표에 대해 조합(Combination)으로 경우의 수를 구해 후보군을 구한다. 후보군을 구하였다면 후보군을 모두 순회하면서 공격 가능한 거리에 따라 적을 제거하고 적이 앞으로 움직이는 과정을 반복하여 제거한 적의 수를 비교하여 최대 값을 찾으면 된다. 문제를 보고, 생각해는데 까지 시간이 걸렸으며 적을 이동시키거나 하는 부분에서 다른 사람들의 코드를 참조하여 풀었다.

 

코드

from sys import stdin
from copy import deepcopy


# combination
def dfs(cur_idx, depth):
    global candidates

    if cur_idx > M:
        return

    if len(check) == depth:
        candidates.append([archer_position[idx] for idx in check])
        return

    for idx in range(cur_idx, M):
        if idx in check:
            continue
        check.append(idx)
        dfs(cur_idx + 1, depth)
        check.pop()


def get_distance(cur_candidate):
    ret = []

    for position in cur_candidate:
        temp = []
        for y in range(N):
            for x in range(M):
                cur_distance = abs(position[0] - y) + abs(position[1] - x)
                if cur_distance <= D:
                    temp.append((cur_distance, y, x))
        ret.append(temp)

    return ret


def forward_enemy():
    return set((y + 1, x) for y, x in enemy if y + 1 < N)


def find_enemy(archer, cur_enemy):
    # 거리와, 좌측에 있는 순으로 정렬
    archer.sort(key=lambda x: (x[0], x[2]))

    for dist, y, x in archer:
        if (y, x) in cur_enemy:
            return (y, x)

    return None


if __name__ == '__main__':
    answer = -1
    N, M, D = map(int, stdin.readline().split())
    enemy = set()
    board = [[0 for _ in range(M)] for _ in range(N)]
    # 입력 값 중 1은 적이 있는 위치
    for y in range(N):
        info = list(map(int, stdin.readline().split()))
        for x in range(M):
            if info[x]:
                enemy.add((y, x))

    check = []
    archer_position = [(N, i) for i in range(M)]
    candidates = []

    dfs(0, 3)

    for archers in candidates:
        sum_kill = 0
        cur_archer_distance = get_distance(archers)
        origin_enemy = deepcopy(enemy)

        while enemy:
            cur_kill = set()

            for cur_archer in cur_archer_distance:
                kill = find_enemy(cur_archer, enemy)

                if kill is not None:
                    cur_kill.add(kill)

            sum_kill += len(cur_kill)
            # 죽은 적들을 제외
            enemy -= cur_kill
            enemy = forward_enemy()

        # 다음 조합을 위해 원래대로 초기화
        enemy = origin_enemy
        answer = max(answer, sum_kill)

    print(answer)