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

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

17135번: 캐슬 디펜스

함수 설명

1. solve: 메인 함수로 재귀 함수로 3명의 궁수를 놓는방식

2. remove_enemy_count : 궁수가 제거한 적의 개수를 반환하는 함수

3. bfs : 거리가 D이하인 적 중에서 가장 가까운 적의 위치를 반환하는 함수

4. check :  적이 아예 없으면 True를 반환하는 함수

from collections import deque
from copy import deepcopy
n,m,d = map(int, input().split())
data = [list(map(int, input().split())) for _ in range(n)]
data.append([0] * m)
dx = [0,1,0,-1]
dy = [1,0,-1,0]
# 궁수가 공격하는 적은 거리가 D이하인 적 중 가장 가까운 적
def check(data):
    for i in range(n):
        for j in range(m):
            if data[i][j] == 1:
                return False
    return True

def bfs(x,y,data):
    queue = deque()
    queue.append((x,y))
    check = {(x,y):1}
    point = []
    nque = deque()
    distance = 0
    while 1:
        while queue:
            x,y = queue.popleft()
            for i in range(4):
                nx,ny = x+dx[i],y+dy[i]
                if 0<=nx<n and 0<=ny<m and check.get((nx,ny)) is None:
                    check[(nx,ny)] = 1
                    if data[nx][ny] == 1:
                        point.append((nx,ny))
                    else:
                        nque.append((nx,ny))
        distance += 1
        if distance > d:
            return -1,-1
        if point:
            if len(point) > 1:
                point = sorted(point, key=lambda x: x[1])
            return point[0][0],point[0][1]
        else:
            queue = nque
            nque = deque()

def remove_enemy_count(data):
    count = 0
    while 1:
        # 공격하고
        enemy = set()
        for j in range(m):
            if data[n][j] == 2:
                e_x,e_y = bfs(n,j,data)
                if e_x != -1:
                    enemy.add((e_x,e_y))
        count += len(enemy)
        for x,y in enemy:
            data[x][y] = 0

        # 적이 이동
        for i in range(n-1,-1,-1):
            for j in range(m):
                if data[i][j] == 1:
                    data[i][j] = 0
                    if i != (n-1):
                        data[i+1][j] = 1
        if check(data):
            return count


answer = 0
def solve(count,data):
    global answer
    if count == 3:
        data = deepcopy(data)
        answer = max(answer, remove_enemy_count(data))
        return

    for i in range(m):
        if data[n][i] == 0:
            data[n][i] = 2
            solve(count + 1,data)
            data[n][i] = 0

solve(0,data)
print(answer)