[백준] 17135: 캐슬 디펜스 (Python)

문제

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

접근 방법

1. 성에 3명의 궁수를 배치할수 있는 모든 경우의수 체크
2. 가장 가까운 적 우선으로 잡음 ( 여러명이라면 가장 왼쪽 적 )

풀이 코드

from collections import deque
import copy

def BFS(can,cattle,r,c):
    dd = (
        (0,-1),
        (-1,0),
        (0,1)
    )

    for dr,dc in dd:
        if not(0 <= r + dr < R and 0 <= c + dc < C):
            continue

        if cattle[r+dr][c+dc]:
            can.append((r+dr, c+dc))
        
        if (r+dr,c+dc) not in vis:
            que.append((r+dr,c+dc))
            vis.add((r+dr,c+dc))
    
    return can


def archer(arr):
    result = 0 # 잡은 적 수
    ene = [()] * 3
    cattle = copy.deepcopy(world) # 성 복사
    
    for _ in range(raw): # 최고 적 높이
        for i in range(3): # 각 궁수만큼 반복
            can = [(-1,-1)]
            que.clear() # 초기화
            vis.clear()
            que.append((R,arr[i])) # 시작점
            vis.add((R,arr[i]))
            
            d = 1 # 사격 사거리

            while que: # BFS
                if d > D: # 사거리 밖이면
                    break
                
                for _ in range(len(que)):
                    can = BFS(can,cattle,*que.popleft())

                d += 1 # 사격 사거리

                vis.clear()
                if len(can) > 1: # 사격가능한 적이 추가됬을때
                    break
            
            can.sort(key=lambda x:(x[1],x[0])) # 왼쪽적 우선 정렬
            if len(can) > 1: # 사격가능한 적이 있다면
                ene[i] = can[1]
            else: # 없다면 초기값 -1,-1
                ene[i] = can[0]

        for r, c in ene: # 각 궁수가 잡을 수 있는 적들 제거
            if r != -1 and c != -1 and cattle[r][c]: # 제거할수 있다면
                cattle[r][c] = 0
                result += 1 # 잡은 적수 추가
        
        cattle = [[0]*C] + cattle[:-1] # 적들이 다가옴
    
    return result # 잡은 적수 반환


R, C, D = map(int,input().split())
world = [0] * R
raw = 0 # 적중 최고 높이 기록할 변수
for r in range(R):
    world[r] = list(map(int,input().split()))
    if not raw and world[r].count(1): # 최고 높이 기록이 안되어있고, 처음 적이 나왔을 때
        raw = R - r

mx = 0
que = deque()
vis = set()

for one in range(C-2):
    for two in range(one+1,C-1):
        for three in range(two+1,C):
            now = archer([one,two,three])
            if mx < now:
                mx = now
print(mx)