문제 링크

캐슬 디펜스

문제 설명

N*M 크기의 보드가 있고, 각 칸에는 적이 1명 존재할 수도 있고 없을 수도 있다. (빈칸:0, 적:1) N+1번째 행에는 성이 있는데, 성에 궁수 3명을 배치해서 사정거리 D 이하의 적 중 가장 가까운 적을 사살하려고 한다. 하나의 칸에는 1명의 궁수만 존재할 수 있고, 최소 사정거리를 갖는 적이 2명 이상이라면 가장 왼쪽에 존재하는 적을 사살한다. 거리는 두 위치 (r1, c1), (r2, c2)에 대해 |r1-r2| + |c1-c2|이다.
사살한 적은 보드에서 사라지고, 공격 후에는 각각의 적들이 성쪽으로 한칸 이동한다. 성에 도달한 적은 마찬가지로 보드에서 사라진다.
격자판의 상태가 주어졌을 때, 궁수의 공격으로 제거할 수 있는 적의 최대 수는?

문제 풀이

세세한 조건이 까다로운 구현문제였다.
$3 ≤ N, M ≤ 15$로, N과 M의 범위가 크지 않아서 combinations를 사용하여 가능한 모든 궁수 배치 경우를 검사했다.
구현해야할 조건의 흐름은

각 궁수 배치의 경우에서

1. 공격하기
   1.1 모든 적에 대해서 궁수1, 궁수2, 궁수3의 위치 기준 사정거리 D이하인 적중 가장 가깝고 왼쪽에 있는 적들을 찾는다.
   1.2 공격한 적은 보드에서 지운다.
2. 이동하기
   보드에 남아있는 적을 성 방향으로 한칸씩 이동시킨다. (y축 + 1)
   만약, 이동시킨 적이 성에 도달하면 보드에서 지운다.
3. 보드에 적이 있는지 검사
   적이 한명도 없으면 해당 궁수배치 경우에 대해서 사살한 적의 count를 전체 최대값과 비교해서 갱신한다.

여기서 제일 까다로웠던 구현 부분은 아무래도 세세한 조건이 많은 공격하기였다.
일단 적들의 좌표는 보드의 상태를 입력받을때 enemies 배열에 저장하였고, 매 궁수 배치 경우에 대해 deepcopy를 이용해서 원본 위치를 훼손하지 않고 보드에서 제외하고 이동시키는 등의 조작을 했다.

 cur_enemies = copy.deepcopy(enemies, key = lambda x : (-x[0], x[1]))

정렬을 한 이유는 최소 사정거리에 위치한 적 중 "가장 왼쪽에 있는 적"을 선택하기 위해서였다. 그런데 뭔가 빠진 조건이 있는지 정렬만 하고 가장 왼쪽인지 검사하지 않으면 틀렸습니다가 나온다 ^_ㅠ..

공격할 적을 찾는 부분에서는 cur_enemies의 모든 적들에 대해서 각 궁수부터 적까지의 거리를 계산하고, 이 값이 1. 주어진 사정거리 D 이하인지 2. 현재까지 해당 궁수의 최소 사정거리인지 3. 최소라면 가장 왼쪽에 있는 적이 맞는지 검사했다.

#1. 공격하기
        D1, D2, D3 = N+M, N+M, N+M
        enemy1, enemy2, enemy3 = [0,0], [0,0], [0,0]
        #공격할 적 찾기
        for enemy in cur_enemies:
            #현재 체크하는 적 위치~각 궁수 위치까지의 거리
            d1 = abs(N-enemy[0]) + abs(arc1-enemy[1])
            d2 = abs(N-enemy[0]) + abs(arc2-enemy[1])
            d3 = abs(N-enemy[0]) + abs(arc3-enemy[1])

            if D1 > d1 and d1 <= D:
                #현재까지의 최소 거리이면
                D1 = d1
                enemy1 = enemy
            elif D1 == d1 and d1 <= D:
                if enemy1[1] > enemy[1]:
                    D1 = d1
                    enemy1 = enemy
            if D2 > d2 and d2 <= D:
                #현재까지의 최소 거리이면
                D2 = d2
                enemy2 = enemy
            elif D2 == d2 and d2 <= D:
                if enemy2[1] > enemy[1]:
                    D2 = d2
                    enemy2 = enemy
            if D3 > d3 and d3 <= D:
                #현재까지의 최소 거리이면
                D3 = d3
                enemy3 = enemy
            elif D3 == d3 and d3 <= D:
                if enemy3[1] > enemy[1]:
                    D3 = d3
                    enemy3 = enemy
        
        #찾은 적에 대해서 공격
        shot = set()
        if enemy1 != [0,0]:
            shot.add((enemy1[0], enemy1[1]))
            if enemy1 in cur_enemies:
                cur_enemies.remove(enemy1)
        if enemy2 != [0,0]:
            shot.add((enemy2[0], enemy2[1]))
            if enemy2 in cur_enemies:
                cur_enemies.remove(enemy2)
        if enemy3 != [0,0]:
            shot.add((enemy3[0], enemy3[1]))
            if enemy3 in cur_enemies:
                cur_enemies.remove(enemy3)
        count += len(shot)

사살할 적에 대한 count는 각 궁수가 같은 적을 사살할 수 있기때문에 set을 이용해서 계산했다.

적들의 이동이나 보드에 적이 존재하는지 여부를 체크하는 부분은 이지,,

import sys
import copy
from itertools import combinations

N, M, D = map(int, input().split())
board = []
answer = 0
enemies = []
for i in range(N):
    tmp = list(map(int, input().split()))
    for j in range(M):
        if tmp[j] == 1:
            enemies.append([i,j])
    board.append(tmp)

num = [i for i in range(M)]
#가능한 궁수 배치 경우
archers = list(combinations(num, 3))

for arc1, arc2, arc3 in archers:
    cur_enemies = copy.deepcopy(enemies, key = lambda x : (-x[0], x[1]))
    count = 0
    while True:
        #1. 공격하기
        D1, D2, D3 = N+M, N+M, N+M
        enemy1, enemy2, enemy3 = [0,0], [0,0], [0,0]
        #공격할 적 찾기
        for enemy in cur_enemies:
            #현재 체크하는 적 위치~각 궁수 위치까지의 거리
            d1 = abs(N-enemy[0]) + abs(arc1-enemy[1])
            d2 = abs(N-enemy[0]) + abs(arc2-enemy[1])
            d3 = abs(N-enemy[0]) + abs(arc3-enemy[1])

            if D1 > d1 and d1 <= D:
                #현재까지의 최소 거리이면
                D1 = d1
                enemy1 = enemy
            elif D1 == d1 and d1 <= D:
                if enemy1[1] > enemy[1]:
                    D1 = d1
                    enemy1 = enemy
            if D2 > d2 and d2 <= D:
                #현재까지의 최소 거리이면
                D2 = d2
                enemy2 = enemy
            elif D2 == d2 and d2 <= D:
                if enemy2[1] > enemy[1]:
                    D2 = d2
                    enemy2 = enemy
            if D3 > d3 and d3 <= D:
                #현재까지의 최소 거리이면
                D3 = d3
                enemy3 = enemy
            elif D3 == d3 and d3 <= D:
                if enemy3[1] > enemy[1]:
                    D3 = d3
                    enemy3 = enemy
        
        #찾은 적에 대해서 공격
        shot = set()
        if enemy1 != [0,0]:
            shot.add((enemy1[0], enemy1[1]))
            if enemy1 in cur_enemies:
                cur_enemies.remove(enemy1)
        if enemy2 != [0,0]:
            shot.add((enemy2[0], enemy2[1]))
            if enemy2 in cur_enemies:
                cur_enemies.remove(enemy2)
        if enemy3 != [0,0]:
            shot.add((enemy3[0], enemy3[1]))
            if enemy3 in cur_enemies:
                cur_enemies.remove(enemy3)
        count += len(shot)
        #2. 이동시키기
        i = 0
        while cur_enemies:
            if i >= len(cur_enemies):
                break
            cur_enemies[i][0] += 1
            #성에 도달하면
            if cur_enemies[i][0] >= N:
                cur_enemies.remove(cur_enemies[i])
            else:
                i+=1
        #3. 보드에 남은 적 있는지 확인
        if not cur_enemies:
            answer = max(answer, count)
            break

        
print(answer)

전체 코드는 다음과 같다.

느낀점

일단 분류가 bfs인걸로 봐서 최적의 방법은 아닌듯 ㅎ,, 스터디해서 다른 팀원들 풀이 보고 다시 풀어봐야지
이런 세세한 조건을 많이 고려해야 하는 구현 문제는 어렵다,,,,,, 테스트케이스가 여러개 주어져서 찾은 오류가 많음,, 최대한 종이에 수도코드를 짠 다음 코드로 입력하려고 하는데 한번에 모든 조건을 완벽하게 고려해서 코드로 옮겨 적는데에는 내공이 아직 부족한듯 ^_ㅠ
로직은 같게 풀었는데 계속 틀렸습니다가 나와서,, 좀 쉬다가 다시 푸니까 맞출 수 있었다, , 푸는 속도도 계속 하면 빨라 지겠쥬,,