[ 17135 ] [ BFS + Combination ] 캐슬 디펜스

 

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

17135번: 캐슬 디펜스

 

---

풀이 과정

---

1. 문제를 잘 읽자.. 궁수들이 서로 다른 적만을 공격하는줄 알고 문제를 풀었다가 계속 틀렸다.. 맞왜틀 맞왜틀 하면서 무한 제출 하지 말자.. 
2. 두가지 단계로 문제를 풀이한다.
   1. 궁수들이 적들에게 활을 쏘는 단계
   2. 격자판을 한칸 밑으로 내리는 단계
3. 적들에게 활을 쏠 때, 각각의 궁수들이 맞추는 최단 거리의 적들 중, 가장 왼쪽에 있는 적을 골라야 하며, 3명의 궁수가 동시에 활을 쏘므로, 같은 적을 맞출수도 있으므로 중복을 카운팅하지 않도록 처리해주어야 하는게 포인트
4. 궁수의 위치같은 경우 최대 3명 배치 가능하므로 [0~M-1]까지의 리스트로 요소의 개수가 3개인 조합을 만들어준 다음 각각의 조합에 대해 시뮬레이션을 진행한다.
5. 시뮬레이션 해보면서 최대로 제거할수 있는 적의 수를 갱신한다.

---

소스 코드

---

import sys
import copy
from collections import deque
from itertools import combinations

input = lambda : sys.stdin.readline().rstrip()

N, M, D = map(int, input().split())
matrix = [list(map(int, input().split())) for _ in range(N)]

def movement_one_time(matrix):
    # 전체 배열 한칸씩 내림
    row, col = len(matrix), len(matrix[0])
    for j in range(col):
        for i in range(row-1, 0, -1):
            matrix[i][j] = matrix[i-1][j]

    for j in range(col):
        matrix[0][j] = 0

def kill_target(matrix, arthor_pos, attack_range):
    queue = deque([[arthor_pos[0], arthor_pos[1], 0]])
    visited = set((arthor_pos[0], arthor_pos[1]))
    ans_cost = -1
    dx = [0, -1, 0]
    dy = [-1, 0, 1]
    answer_list = []
    while queue:
        x, y, cost = queue.popleft()
        
        if cost == attack_range:
            continue
        
        if matrix[x][y] == 1:
            if ans_cost == -1:
                ans_cost = cost
                answer_list.append([x, y])
            else:
                if ans_cost == cost:
                    answer_list.append([x, y])
            continue

        for i in range(3):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx and nx < len(matrix) and 0 <= ny and ny < len(matrix[0]) and \
               (nx, ny) not in visited:
                visited.add((nx, ny))
                queue.append([nx, ny, cost+1])

    if len(answer_list) == 0:
        return None

    # 가장 왼쪽에 있는 적 찾는 부분
    min_left = int(10e9)
    min_index = 0
    for i in range(len(answer_list)):
        if answer_list[i][1] < min_left:
            min_index = i
            min_left = answer_list[i][1]
            
    target_x, target_y = answer_list[min_index]
    return [target_x, target_y]
                

all_case = list(combinations([i for i in range(M)], 3))

answer = 0
for case in all_case:
    test_matrix = copy.deepcopy(matrix)
    kill_count = 0
    for i in range(N):
        kill_set = set()
        for archor in case:
            P = kill_target(test_matrix, [N-1, archor], D)
            if P is not None:
                target_x, target_y = P
                kill_set.add((target_x, target_y))
        for x, y in kill_set:
            test_matrix[x][y] = 0
        kill_count += len(kill_set)
        movement_one_time(test_matrix)
    answer = max(answer, kill_count)

print(answer)