[Python] Baekjoon - 17135. 캐슬 디펜스

백준의 17135번 캐슬 디펜스 문제는 그래프 탐색 및 브루트 포스 알고리즘을 이용하여 푸는 문제이다. 성 안에 있는 3명의 궁수가 성 밖의 적을 매 턴 공격하며 게임에서 최대로 무찌를 수 있는 적의 수를 구하는 문제이다.

 

문제 정보

알고리즘 분류

• 그래프 탐색
• 브루트포스

난이도

• 골드 4

캐슬 디펜스 문제 요약

• NxM 크기의 격자 칸에는 칸마다 최대 한명의 적이 있을 수 있고, 격자칸 아래 N+1행은 궁수를 배치할 수 있는 성이다.
• 궁수는 거리 D 이하(맨해튼 거리)의 적 중 가장 가까운 적(거리가 같다면 가장 왼쪽에 있는 적)을 한 턴에 한 명씩 공격할 수 있다. 모든 궁수는 동시에 공격하며, 여러 궁수가 같은 적을 공격할 수도 있다.
• 한 턴이 지나면 모든 적들은 한 칸씩 내려온다. 성에 들어온 적은 게임에서 제외하며, 모든 적이 제외되면 게임이 종료된다.
• 궁수를 3명만 배치하려고 할 때, 게임에서 무찌를 수 있는 적의 최대 수를 구하기

문제 풀이

과정

• 우선 N+1행의 M개의 칸 각각에 궁수가 배치되었을 때, 각 차례에 무찌를 수 있는 적의 위치를 순서대로 구하여 저장했다.
• 행/열의 최대 크기가 15이기 때문에, 브루트 포스를 이용해도 풀 수 있을 것이라 생각했다. 따라서 MC3만큼의 경우의 수에 대하여 각각의 경우에 무찌를 수 있는 적의 수를 구하고, 최댓값을 반환하도록 했다.

풀이

• get_killable_enemy(archer_r, archer_c): 궁수의 행/열이 주어졌을 때, 이 궁수가 매 차례 때 무찌를 수 있는 적을 순서대로 구하는 함수
• execute_game(archers): 세명의 궁수의 위치가 주어졌을 때, 매 차례에 각 궁수가 적을 물리치고 최종적으로 물리친 적의 수를 반환하는 함수

코드

from collections import deque
from itertools import combinations


def get_killable_enemy(archer_r, archer_c):
    global M, D, board

    visited = [[0 for _ in range(M)] for _ in range(archer_r+1)]
    dr, dc = [0, -1, 0], [-1, 0, 1]
    res = []

    queue = deque()
    queue.append((archer_r, archer_c, 0))
    visited[archer_r][archer_c] = 1

    while len(queue) > 0:
        here_r, here_c, here_dist = queue.popleft()

        if here_dist >= D:
            continue

        # 왼쪽, 위, 오른쪽 방문 확인
        for d in range(3):
            next_r, next_c = here_r + dr[d], here_c + dc[d]
            if 0 <= next_r < archer_r and 0 <= next_c < M and not visited[next_r][next_c]:
                # 다음 위치에 적이 있으면 결과 배열에 추가
                if board[next_r][next_c] == 1:
                    res.append((next_r, next_c))

                # 방문 표시하고 큐에 추가
                visited[next_r][next_c] = 1
                queue.append((next_r, next_c, here_dist+1))

    return res


def execute_game(archers):
    global N, M, kill

    # 게임에서 제외된 적들의 좌표
    killed = set()

    # 매 차례마다
    for turn in range(N):
        # 이번 차례에서 무찌른 적들의 좌표
        killed_this_turn = set()

        # 각 궁수마다
        for archer in archers:
            # 이번 차례에 무찌를 수 있는 적 중 아직 제외되지 않은 첫번째 적을 무찌른다.
            for enemy in kill[archer][turn]:
                if enemy not in killed:
                    killed_this_turn.add(enemy)
                    break

        # 이번 차례에서 무찌른 적들 제외하기
        killed = killed | killed_this_turn

    return len(killed)


def get_kill_cnt():
    global N, M, D, board, kill

    res = 0

    # 각 위치의 궁수가 무찌를 수 있는 적들의 좌표를 구한다.
    for r in range(N, 0, -1):
        for c in range(M):
            kill[c].append(get_killable_enemy(r, c))

    # 궁수를 배치하는 모든 경우의 수에 대해 무찌른 적의 수를 구한다.
    comb = list(combinations([i for i in range(M)], 3))
    for archers in comb:
        res = max(res, execute_game(archers))

    return res


if __name__ == '__main__':
    N, M, D = map(int, input().split())
    board = [list(map(int, input().split())) for _ in range(N)]
    board.append([0 for _ in range(M)])
    kill = [[] for _ in range(M)]

    print(get_kill_cnt())