문제
캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 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
출력
첫째 줄에 궁수의 공격으로 제거할 수 있는 적의 최대 수를 출력한다.
전체 코드
from itertools import combinations
from collections import deque
import copy
n, m, d = list(map(int, input().split()))
arr = [[0] * m for _ in range(n + 1)]
ENEMY = 1
NONE = 0
answer = 0
turn = m + 1
positions = []
for i in range(n):
data = list(map(int, input().split()))
for j in range(m):
arr[i][j] = data[j]
positions.append((i, j))
if arr[i][j] == 1:
turn = min(turn, i)
# 최대 시행 횟수
turn = n - turn
columns = [i for i in range(m)]
comb = list(combinations(columns, 3))
# 스택을 이용해 아래로 1칸씩 적을 이동시킨다.
def move_enemy(origin: list[list[int]]):
line_stack = dict()
for k in range(m):
line_stack[k] = deque()
line_stack[k].append(0)
# 맨 아랫줄은 제외하고 스택에 넣는다.
for a in range(n - 1):
for b in range(m):
line_stack[b].append(origin[a][b])
for a in range(n):
for b in range(m):
origin[n - a - 1][b] = line_stack[b].pop()
def find_nearest(archer_y: int, origin: list[list[int]]):
pos_set = set()
for a in range(n + 1):
for b in range(m):
difference = abs(n - a) + abs(archer_y - b)
if difference <= d and origin[a][b] == ENEMY:
pos_set.add((difference, a, b))
pos_list = list(sorted(pos_set, key=lambda o: (o[0], o[2])))
if pos_list:
return pos_list[0][1], pos_list[0][2]
else:
return None
def find_enemy(result, origin: list[list[int]]) -> list:
target = set()
for y in result:
nearest = find_nearest(y, origin)
if nearest is not None:
target.add((nearest[0], nearest[1]))
return list(target)
for rst in comb:
score = 0
temp = copy.deepcopy(arr)
for count in range(turn):
target_list = find_enemy(rst, temp)
for p, q in target_list:
temp[p][q] = NONE
score += len(target_list)
move_enemy(temp)
answer = max(answer, score)
print(answer)
해설
1.문제 제대로 이해하기
예제 5 입력을 예시로 들어보자.
6 5 1
1 0 1 0 1
0 1 0 1 0
1 1 0 0 0
0 0 0 1 1
1 1 0 1 1
0 0 1 0 0성과 궁수의 위치
6 * 5 배열을 기준으로 했을 때, 행을 하나 더 늘려서 7 x 5 배열을 만든다. 그리고 마지막 행에 성이 존재한다.
따라서 문제에 기재된대로, 마지막 행에서만 궁수를 배치할 수 있다.
궁수의 배치는 단 한 번 뿐이다.
게임 설명에서 보다시피 궁수를 배치한 이후의 게임 진행은 정해져있다 라는 문제 설명이 있다. (개인적으로 굉장히 이해가 어려웠던 부분이다.)
이 말의 뜻은, 배치가 한 번 정해지면, 게임이 종료될때 까지 고정이다라는 뜻이다...
예를 들어, 위 그림에서 처음에 (0,1,3)열에 배치했다고 하자. 그러면 게임이 끝날 때까지 궁수는 계속 (0,1,3)열의 마지막 행에 있게 된다. 따라서 조합은 처음 한 번만 사용된다.
2. 가장 가까운 적 찾기
def find_nearest(archer_y: int, origin: list[list[int]]):
pos_set = set()
for a in range(n + 1):
for b in range(m):
difference = abs(n - a) + abs(archer_y - b)
if difference <= d and origin[a][b] == ENEMY:
pos_set.add((difference, a, b))
pos_list = list(sorted(pos_set, key=lambda o: (o[0], o[2])))
if pos_list:
return pos_list[0][1], pos_list[0][2]
else:
return None일단, set을 이용하여 중복 좌표를 걸러낼 필요가 있다. 그리고 수집된 자표들은 수집할 때마다 처리해선 안되고, 수집이 끝나고 나서 한 꺼번에 처리해야 한다.
같은 적이 여러 궁수에게 공격당할 수 있다. 라는 조건 때문이다.
배열 전체를 순회하면서, (x,y) 좌표의 절댓값 차이가 d 이하이고 '적'이라면 set에 수집한다.
마지막으로 중요한 것은 '정렬'이다.
궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다. 라는 조건에 의해 거리 순으로 정렬한 후, y좌표 순으로 정렬해야 한다.
3. 블록 아래로 내리기
테트리스 같은 이차원 배열 시뮬레이션에서 많이 나오는 요구사항이다.
# 스택을 이용해 아래로 1칸씩 적을 이동시킨다.
def move_enemy(origin: list[list[int]]):
line_stack = dict()
for k in range(m):
line_stack[k] = deque()
line_stack[k].append(0)
# 맨 아랫줄은 제외하고 스택에 넣는다.
for a in range(n - 1):
for b in range(m):
line_stack[b].append(origin[a][b])
for a in range(n):
for b in range(m):
origin[n - a - 1][b] = line_stack[b].pop()코드에서 line_stack은 각 행마다 stack을 갖고 있는 dict이다. 그림으로 표현하면 다음과 같다.
각 열의 스택은 특성 상 LIFO다. 그리고 아래로 내리면 맨 윗 행의 경우는 0으로 채워져야 한다. 따라서 0을 먼저 채워 넣자.
맨 아랫 줄 제외하고 순회해서 각 열의 스택에 담으면 다음과 같다.
(맨 아랫 줄을 제외하는 이유는 어차피 없어지기 때문이다.)
스택이기 때문에 이를 pop해서 원래 배열에 되돌려 놓으면 블록을 내릴 수 있게 된다.
다시 풀기 1회차
정답 코드
import sys
import copy
from collections import deque
from itertools import combinations
ENEMY = 1
EMPTY = 0
INVALID = -1
n, m, d = list(map(int, sys.stdin.readline().split()))
arr = [[0] * m for _ in range(n + 1)]
for i in range(n):
data = list(map(int, sys.stdin.readline().split()))
for j in range(m):
arr[i][j] = data[j]
# 왼, 위, 아래, 오른쪽
DX = [0, -1, 1, 0]
DY = [-1, 0, 0, 1]
def exist_enemy(array: list[list[int]]) -> bool:
for a in range(n+1):
for b in range(m):
if array[a][b] == ENEMY:
return True
return False
# 각 궁수가 한 명씩 쏴봄. 반환은 잡은 적의 좌표
def attack_enemy(archer_x: int, archer_y: int, array: list[list[int]]):
visited = [[False] * m for _ in range(n + 1)]
queue = deque()
queue.append((archer_x, archer_y, 0))
visited[archer_x][archer_y] = True
while queue:
x, y, count = queue.popleft()
if array[x][y] == ENEMY:
return x, y
for direction in range(4):
adj_x = x + DX[direction]
adj_y = y + DY[direction]
if adj_x < 0 or adj_x >= n + 1 or adj_y < 0 or adj_y >= m:
continue
if not visited[adj_x][adj_y] and count + 1 <= d:
visited[adj_x][adj_y] = True
queue.append((adj_x, adj_y, count + 1))
return INVALID, INVALID
def remove_enemy(targets: list, array: list[list[int]]):
new_array = copy.deepcopy(array)
for x, y in targets:
new_array[x][y] = EMPTY
return new_array
def move_enemy(array: list[list[int]]):
new_array = [[0] * m for _ in range(n + 1)]
for a in range(1, n + 1):
for b in range(m):
if a != n:
new_array[a][b] = array[a - 1][b]
return new_array
def print_array(array: list[list[int]]):
for a in range(n + 1):
for b in range(m):
print(array[a][b], end=' ')
print()
print()
answer = 0
xys = [[n, i] for i in range(m)]
# 궁수 (x,y)의 조합 만들기. 최대 m C 3
archer_combination = list(combinations(xys, 3))
# 궁수 조합 각각에 대해 시뮬레이션 해보기
for archers in archer_combination:
new_arr = copy.deepcopy(arr)
removed_count = 0
while exist_enemy(new_arr):
# 같은 적이 여러 궁수에게 공격당할 수 있다는 조건에 의해 중복 제거가 필요하다.
removed_enemy = set()
for archer in archers:
removed = attack_enemy(archer_x=archer[0], archer_y=archer[1], array=new_arr)
if removed != (INVALID, INVALID):
removed_enemy.add(removed)
if removed_enemy:
removed_count += len(removed_enemy)
new_arr = remove_enemy(targets=list(removed_enemy), array=new_arr)
new_arr = move_enemy(array=new_arr)
answer = max(answer, removed_count)
print(answer)
해설
예전에 풀이했을 때는 스택을 이용했었는데, 너무 장황하고 복잡한 방법이었다.
블록을 내리는 것은 다음과 같이 단순히 배열 인덱스만 잘 활용하면 된다.
def move_enemy(array: list[list[int]]):
new_array = [[0] * m for _ in range(n + 1)]
for a in range(1, n + 1):
for b in range(m):
if a != n:
new_array[a][b] = array[a - 1][b]
return new_array