09/04 캐슬 디펜스 BOJ 17135 파이썬

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

17135번: 캐슬 디펜스

1. 풀이

삼성 A형 기출 문제/구현과 브루트포스

반복문이 다음과 같은 방식으로 진행된다.

궁수의 배치를 바꿔가면서 아래를 진행한다.

 1. 공격할 대상 찾기

 2. 공격

 3. 적 좌표 업데이트

 4. 공격한 대상 제거

 

게임 맵 전체를 갖고 연산을 수행하는게 아니라  목표를 갖는 배열을 따로 만들어서 관리하는게 낫다

 

def calc_distance(case):
 	#궁수별 공격가능한 좌표를 찾아서 저장해준다.
    possible_attack_area=[[],[],[]] #궁수가 세명 
    for idx, archer in enumerate(case): #각 궁수에 대해 전체 맵을 돌면서
        for row in range(N): 
            for col in range(M):
            #해당 궁수와 적 사이의 거리를 계산하고 그 값이 거리제한보다 작거나 같으면 (거리, 행, 열)의 형태로 저장
                dist = abs(archer[0]- row)+ abs(archer[1]-col) 
                if dist <= D: 
                    possible_attack_area[idx].append((dist, row, col))

    return possible_attack_area



def find_enemy(possible_attack_area, enemy):
	# row, col 값이 적군이 있는 좌표값이면 좌표값을 리턴
    #공격가능한 영역을 거리와 열 순으로 정렬하고 enemy에 그 값이 있으면 값을 리턴해준다.
    possible_attack_area.sort(key = lambda x :(x[0], x[2])) 
    for dist, row, col in possible_attack_area:
        if (row, col) in enemy:
            return (row, col)
    return None #없으면 안함

def go_forward(enemy):
	# 값을 업데이트해준다.
    return set([(row+1,col) for row,col in enemy if row+1 < N])

import copy
N,M,D= map(int, input().split())
Castle = [input().split() for i in range(N)] + [[0 for i in range(M)]]

Enemy=set()
for i in range(N):
    for j in range(M):
        if Castle[i][j] == '1':
            Enemy.add((i,j))


archer=[[(N,i),(N,j),(N,k)] for i in range(M) for j in range(i+1,M) for k in range(j+1, M)]

answer=0
for case in archer:
    temp_answer=0
    castle = copy.deepcopy(Castle)
    possible_attack_areas = calc_distance(case)
    enemy = copy.deepcopy(Enemy)

    while enemy:
        temp=set()
        for possible_attack_area in possible_attack_areas:
            loc_enemy = find_enemy(possible_attack_area, enemy)
            if loc_enemy is not None:
                temp.add(loc_enemy)

        temp_answer += len(temp)

        enemy -= temp
        enemy = go_forward(enemy)

    if answer < temp_answer:
        answer = temp_answer

print(answer)

 

# 궁수자리 3개 뽑는거
def location(idx=-1,num=3,position=[]):
    global M,ans

    if num==0:
        cnt = defence(position)
        ans= max(ans,cnt)
        return

    for i in range(idx+1,M-num+1):
        position.append(i)
        location(i,num-1,position)
        position.pop()

# 궁수 전진
def defence(position):
    global N,M
    # 복제
    enemy_copy = [0] * N
    for i in range(N):
        enemy_copy[i] = enemy[i][:]

    cnt_attack=0
    arc1 ,arc2, arc3 = position
    for i in range(N-1,-1,-1):
        a = shoot(i, arc1 , enemy_copy)
        b = shoot(i, arc2 , enemy_copy)
        c = shoot(i, arc3 , enemy_copy)
        attack = set()
        if a: attack.add((a[0],a[1]))
        if b: attack.add((b[0], b[1]))
        if c: attack.add((c[0], c[1]))
        cnt_attack+=len(attack)
        for j,k in attack:
            enemy_copy[j][k]=0
    return cnt_attack

# 발사
# 같은 거리일 때 가장 왼쪽에 있는 적 공격
# 화살 발사하고 삼각형을 그린다고 생각하면 된다.
def shoot(a, b, enemy_copy):
    global N,M,D
    if enemy_copy[a][b]==1:
        return (a,b)

    arrow=[(a,b,1)]
    st=0
    while arrow:
        r,c,d=arrow[st]
        st+=1
        if d>D:
            return False
        for nr,nc in (r,c-1),(r-1,c),(r,c+1):
            if not(0<=nr<N and 0<=nc<M): continue
            if (nr,nc,d+1) in arrow: continue
            if enemy_copy[nr][nc]==1:
                if d+1>D:
                    continue
                return (nr,nc)
            else:
                arrow.append((nr,nc,d+1))
        if st==len(arrow):      # st가 인덱스 초과한것
            return False
    # return False


N,M,D=map(int,input().split())
enemy=[list(map(int, input().split())) for _ in range(N)]

ans=0
location()
print(ans)