[문제 바로가기] https://www.acmicpc.net/problem/17135
📌문제 설명
캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 N×M인 격자판으로 나타낼 수 있다. 격자판은 1×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나이다. 격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다.
성을 적에게서 지키기 위해 궁수 3명을 배치하려고 한다. 궁수는 성이 있는 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다. 각각의 턴마다 궁수는 적 하나를 공격할 수 있고, 모든 궁수는 동시에 공격한다. 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다. 같은 적이 여러 궁수에게 공격당할 수 있다. 공격받은 적은 게임에서 제외된다. 궁수의 공격이 끝나면, 적이 이동한다. 적은 아래로 한 칸 이동하며, 성이 있는 칸으로 이동한 경우에는 게임에서 제외된다. 모든 적이 격자판에서 제외되면 게임이 끝난다.
게임 설명에서 보다시피 궁수를 배치한 이후의 게임 진행은 정해져있다. 따라서, 이 게임은 궁수의 위치가 중요하다. 격자판의 상태가 주어졌을 때, 궁수의 공격으로 제거할 수 있는 적의 최대 수를 계산해보자.
격자판의 두 위치 (r1, c1), (r2, c2)의 거리는 |r1-r2| + |c1-c2|이다.
입력
첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다.출력
첫째 줄에 궁수의 공격으로 제거할 수 있는 적의 최대 수를 출력한다.제한
- 3 ≤ N, M ≤ 15
- 1 ≤ D ≤ 10
💡 문제 풀이
3명의 궁수를 배치하여 최대한 많은 적을 제거하는 것이 목표다.
3 <= M <= 15 이기 때문에 궁수를 배치할 수 있는 경우의 수는 15C3이다.
큰 값이 아니므로 '조합'을 이용한 완전탐색으로 적을 가장 많이 죽일 수 있는 궁수의 위치를 찾고자 했다.
N x M 의 배열로 입력이 주어지지만 적의 위치가 단순하고 거리를 이용해서 제거할 적을 찾아야하기 때문에 '좌표'로 접근하는 것이 편리하다고 생각했다.
이 때, 단순히 배열을 사용하는것보다 deque 자료구조를 사용하는것이 시간복잡도를 줄여줄 수 있기 때문에 deque를 사용했다.
step 1)
변수를 선언한다.
- answer : 제거한 적의 수를 담는 변수
- rc : 적의 위치를 담는 배열
적의 위치(좌표)를 배열에 담는다.
'조합'을 이용하여 궁수가 위치할 수 있는 모든 경우에 대해 탐색한다.
step 2)
- find 함수 : 3명의 궁수가 제거할 적을 찾는 함수
- kill : 제거한 적의 수
- target : 3명의 궁수가 각자 제거하게 될 적의 좌표를 담는 배열
- dist : 3명의 궁수가 각자 제거하게 될 적과의 거리를 담는 배열
모든 적이 사라질 때 까지(적의 좌표가 담겨있는 deque(rc)에 원소가 존재할 때까지) find함수를 진행한다.
적의 좌표가 담겨있는 deque(rc)에서 원소를 하나씩 빼내어 3명의 궁수가 제거하게 될 적을 찾는다.
이 때, 적의 위치가 3명의 궁수가 모두 제거할 수 있는 범위내에 들어올 수 있기 때문에 3명의 궁수 모두에 대해 따져본다.
- distance : 적과 궁수와의 거리
-
만약, 적이 궁수의 공격 거리 제한내에 들어오면서 이전에 제거하려던 적보다 더 가까운 거리에 있다면
궁수의 target과 dist를 최신화 시켜준다 -
만약, 이전에 제거하려던 적과 같은 거리고 왼쪽에 위치하고 있다면
궁수의 target과 dist를 최신화 시켜준다.
모든 적을 탐색할 때까지 어떠한 적이 제거될지 모르기 때문에 popleft한 enemy는 다시 deque(rc)에 담아둔다.
step 3)
반복문을 마치고 궁수가 제거할 적을 찾았다면 두 가지를 진행해야한다.
1. 선택한 적을 제거해야한다.
2. 제거되지 않은 적들은 아래로 한 칸씩 이동해야한다.
1, 2번을 해결하기 위해서 두 개의 함수를 만들었다.
- move 함수 : 궁수가 제거할 적은 deque에서 제거하고 남은 적들은 아래로 한 칸씩 이동
- check 함수 : 궁수가 제거할 적의 수를 카운트(궁수가 동일한 적을 제거할 수도 있기 때문이다.)
move함수에서는 적의 좌표가 들어있는 deque를 탐색하면서 해당 좌표가 target에 들어있으면 빼주고 그렇지 않으면 아래로 한 칸(행+1) 이동시키면 된다.
아래로 한 칸 이동했을 때 범위를 벗어나도 제거한다.
이후 check 함수에서 제거할 적의 개수를 파악한다.
궁수가 동일한 적을 제거할 경우도 있고 공격 거리 제한으로 적을 제거하지 못할 수도 있다.
따라서, target에 담겨있는 좌표중 초기값([0, inf])이 아니면서 다른 좌표와 동일하지 않는 것을 카운팅한다.
step 4)
move 함수, check 함수를 통해서 변경된 값을 최신화 시켜준다.
모든 적이 제거되거나 빠져나가면 정답을 출력할 answer 변수를 kill값과 비교하여 최대값으로 최신화해준다.
코드는 다음과 같다.
import sys
from copy import deepcopy
from itertools import combinations
from collections import deque
def check(target):
global inf
res = []
for t in target:
if t not in res and t != [0, inf]:
res.append(t)
return len(res)
def move(rc, target):
global N, M
for _ in range(len(rc)):
enemy = rc.popleft()
if enemy in target: continue
if enemy[0]+1 < N:
enemy[0] += 1
rc.append(enemy)
return rc
def find(li, rc):
global answer, N, D, inf
kill = 0
while len(rc):
target = [[0, inf] for _ in range(3)]
dist = [inf] * 3
for _ in range(len(rc)):
enemy = rc.popleft()
for idx in range(3):
distance = abs(enemy[0]-N) + abs(enemy[1]-li[idx])
if distance < dist[idx] and distance <= D:
dist[idx] = distance
target[idx][0], target[idx][1] = enemy[0], enemy[1]
elif distance == dist[idx] and enemy[1] < target[idx][1]:
target[idx][0], target[idx][1] = enemy[0], enemy[1]
rc.append(enemy)
rc = move(rc, target)
kill += check(target)
answer = max(answer, kill)
N, M, D = map(int, input().split())
rc = []
answer = 0
inf = 0xfffff
for r in range(N):
row = list(map(int, sys.stdin.readline().split()))
for c in range(M):
if row[c]:
rc.append([r, c])
for li in combinations([i for i in range(M)], 3):
find(li, deque(deepcopy(rc)))
print(answer)난독증이 있나... 문제가 요구하는 내용을 제대로 이해하지 못해서 엉뚱한 코드를 만들어 시간을 낭비했다...😥
더 많은 문제를 풀어야겠다ㅏㅏ
반례 참고 : https://hoho325.tistory.com/125
