[BOJ] 17135. 캐슬디펜스

www.acmicpc.net/problem/17135

17135번: 캐슬 디펜스

 

문제: 캐슬디펜스에서 궁수가 얼마나 많은 적을 죽일 수 있는가?

 

문제 이해하기!!

한 바둑판에 병사들 여러개 놓고 1초 지날 때마다 한칸씩 전진하는데

마지막 칸의 밖의 칸에서 궁수가 대기타고 있고 그 대기타는 궁수의 범위안에

적이 들어오면 궁수는 쏴 죽입니다. 근데 궁수도 1초에 한 번씩 밖에 못 죽여서

모두를 죽일 수 없는 경우가 생깁니다. 그 때문에 이 문제가 생겼습니다.

즉, 궁수가 있는 칸까지 병사들이 온다면

그 병사들은 그냥 게임에서 제거하고 카운트는 세지않습니다.

궁수가 제거한 병사만 세어서 답을 출력하면 됩니다.

 

---

 

처음엔.. 궁수의 범위를 중점으로 잡고 풀었습니다.

하지만 나중에 다시 생각해보니 궁수의 범위가 중요한 게 아니라

병사의 위치가 중요하더라구요.

병사의 위치만 알면 궁수의 범위는 식 하나로 끝나고

심지어 배열 전체를 탐색하지 않아도 됩니다.

 

브루트포스 방법을 사용하였고, 궁수의 위치는 조합으로 만들었습니다.

 

코드:

from itertools import combinations

N, M, D = map(int, input().split())
arr = [list(map(int, input().split())) for i in range(N)]
loc = []

for i in range(N):
    for j in range(M):
        if arr[i][j] == 1:
            loc.append([i, j])
loc.sort(key=lambda x:x[1])
init = [loc[i][:] for i in range(len(loc))]

ans = []

for com in combinations(range(M), 3):
    loc = [init[i][:] for i in range(len(init))]
    cnt = 0
    while loc:
        get = set()
        for comx in com:
            check = False
            for i in range(1, D+1):
                for x in range(len(loc)):
                    if abs(loc[x][0]-N) + abs(loc[x][1]-comx) <= i:
                        get.add(x)
                        check = True
                        break
                if check:
                    break
        get_res = sorted(list(get), reverse=True)
        for i in get_res:
            loc.pop(i)
            cnt += 1
        get_res = []
        for i in range(len(loc)-1, -1, -1):
            loc[i][0] += 1
            if loc[i][0] == N:
                get_res.append(i)
        for i in get_res:
            loc.pop(i)
    ans.append(cnt)
print(max(ans))