[백준] 17135 캐슬디펜스 python

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

17135번: 캐슬 디펜스

그래프 탐색이 가미된 브루트포스 문제이고 거기에 시뮬레이션까지 덤으로 꽉꽉 담아준다.(궁수 세명을 배치하는 게 브루트포스, 매 턴 확인하는 시뮬레이션, 턴마다 궁수가 죽이는 적을 찾는 게 그래프 탐색이다.)

궁수의 배치 조합을 백트래킹이나 반복문으로 직접 만들수 있긴 하지만 더빠른 itertools.combinations를 사용했다.

궁수의 배치가 끝나면 턴을 진행했다. 매 턴마다 한칸씩 아래로 내려가게 되는데 이를 아래부터 접근해서 위로 탐색했다. 궁수의 위치에서 가장 가까운 적을 찾을 땐 조건에 따라 왼쪽, 위, 오른쪽 순으로 bfs를 진행했다. 그리고 visit을 사용해 찾은 지점은 방문하지 않게 하고, dead라는 것을 사용해 이미 죽은 적이면 다음 사람을 탐색하도록했다. 

궁수별로 bfs가 모두끝나면 한번에 dead에 추가했고 그 다음 턴을 진행하였다.

위의 방식으로 모든 궁수의 배치 조합에서 최대로 죽이는 값을 찾아서 출력하면 된다.

# import sys; input = sys.stdin.readline
from collections import deque
from itertools import combinations
d = [(0, -1), (-1, 0), (0, 1)]  # west/north/east


def bfs(turn, archers):
    global N, M, D, _map, dead
    ret = set()
    for archer in archers:  # [0, 1, 2] => start col
        q = deque()  # add archer's range
        a_pos = (len(_map) - turn, archer)
        q.append((a_pos[0] - 1, archer))
        visit = set()
        while q:
            cur = q.popleft()
            if cur in visit:
                continue
            visit.add(cur)
            if _map[cur[0]][cur[1]] and not dead[cur[0]][cur[1]]:
                ret.add(cur)
                break
            for dr, dc in d:
                nr, nc = cur[0] + dr, cur[1] + dc
                if 0 > nc or nc >= M: continue
                if abs(a_pos[0] - nr) + abs(a_pos[1] - nc) > D: continue
                q.append((nr, nc))
    for r in ret:
        dead[r[0]][r[1]] = 1
    return len(ret)


def main():
    global N, M, D, _map, dead
    N, M, D = map(int, input().split())
    _map = [[0 for _ in range(M)] for _ in range(D - 1)]
    for _ in range(N):
        _map.append(list(map(int, input().split())))
    answer = 0
    for archers in combinations(range(M), 3):
        ans = 0
        dead = [[0 for _ in range(M)] for _ in range(len(_map))]
        for turn in range(N):
            ans += bfs(turn, archers)
        answer = max(answer, ans)
    print(answer)


if __name__ == "__main__":
    main()

---

조건을 잘 읽어봐야하는게 거리가 같을땐 무조건 왼쪽이 우선이어야한다. 처음엔 왼쪽, 오른쪽, 위쪽으로 진행해서 틀렸다.