[백준 17135] 캐슬 디펜스 (Gold 4)

문제

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

접근

1. 궁수가 성에 놓일 경우를 조합으로 구한다.
2. 모든 궁수의 배치에 대해 시뮬레이션을 돌린다.
3. 궁수가 적을 맞추는 것은 bfs로 구현하였다. 조건에 따라 왼쪽, 가운데, 오른쪽 이 순서로 맵을 탐색한다. 이 때 주의할 점은 이미 화살을 맞은 적이 또 화살을 맞을 수 있는 경우가 있으므로 화살을 맞자마자 맵에서 적을 바로 제거를 하면 안된다. 리턴값은 제거된 적의 숫자가 된다.
4. bfs 실행 후 맵을 아래로 내린다.
5. 2 - 4를 맵에 적이 없을 때 까지 반복한다.

Code

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

dx, dy = [-1, 0, 1], [0, -1, 0]


def pass_condition():
    for y in range(n):
        for x in range(m):
            if temp_maps[y][x]:
                return False
    return True


def bfs(archers):
    q = deque()
    cnt = 0
    visit = [[0] * m for _ in range(n + 1)]
    hits = []
    for i in archers:
        q.append((n, i))
        visit[n][i] = 0

        while q:
            y, x = q.popleft()
            for i in range(3):
                cy, cx = y + dy[i], x + dx[i]
                if cy < 0 or cy >= n or cx < 0 or cx >= m:
                    continue

                if temp_maps[cy][cx] and visit[y][x] + 1 <= d:
                    hits.append((cy, cx))
                    q.clear()
                    break

                elif not temp_maps[cy][cx] and visit[y][x] + 1 <= d:
                    visit[cy][cx] = visit[y][x] + 1
                    q.append((cy, cx))

        q.clear()
    while hits:
        y, x = hits.pop()
        if temp_maps[y][x]:
            temp_maps[y][x] = 0
            cnt += 1
    return cnt


def down():
    for y in range(n - 1, -1, -1):
        for x in range(m):
            if y == n - 1:
                temp_maps[y][x] = 0
            else:
                temp_maps[y + 1][x] = temp_maps[y][x]
                if not y and temp_maps[y][x]:
                    temp_maps[y][x] = 0


n, m, d = map(int, sys.stdin.readline().split())
maps = []
temp_maps = None
for _ in range(n):
    maps.append(list(map(int, sys.stdin.readline().split())))
maps.append([0] * m) # 성벽

archers_list = list(combinations(range(0, m), 3))
answer = 0
for archers in archers_list:
    temp_maps = copy.deepcopy(maps)
    summ = 0
    while not pass_condition():
        summ += bfs(archers)
        down()
    answer = max(summ, answer)
print(answer)

여담

1년 전에 이 문제를 풀었을 때는 한 20번은 넘게 틀린 것 같은데, 오늘 2트만에 성공해 기분이 매우 좋은 상태 ㅎㅎ