[BOJ][🟡4][백준#17135] 캐슬 디펜스

문제 출처

BAEKJOON Online Judge #17135

문제

캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 N×M인 격자판으로 나타낼 수 있다. 격자판은 1×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나이다. 격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다. 성을 적에게서 지키기 위해 궁수 3명을 배치하려고 한다. 궁수는 성이 있는 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다. 각각의 턴마다 궁수는 적 하나를 공격할 수 있고, 모든 궁수는 동시에 공격한다. 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다. 같은 적이 여러 궁수에게 공격당할 수 있다. 공격받은 적은 게임에서 제외된다. 궁수의 공격이 끝나면, 적이 이동한다. 적은 아래로 한 칸 이동하며, 성이 있는 칸으로 이동한 경우에는 게임에서 제외된다. 모든 적이 격자판에서 제외되면 게임이 끝난다.  게임 설명에서 보다시피 궁수를 배치한 이후의 게임 진행은 정해져있다. 따라서, 이 게임은 궁수의 위치가 중요하다. 격자판의 상태가 주어졌을 때, 궁수의 공격으로 제거할 수 있는 적의 최대 수를 계산해보자. 격자판의 두 위치 (r1, c1), (r2, c2)의 거리는 |r1-r2| + |c1-c2|이다.

입력

첫째 줄에 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D가 주어진다. 둘째 줄부터 N개의 줄에는 격자판의 상태가 주어진다. 0은 빈 칸, 1은 적이 있는 칸이다.

출력

첫째 줄에 궁수의 공격으로 제거할 수 있는 적의 최대 수를 출력한다.

제한

3 ≤ N, M ≤ 15 1 ≤ D ≤ 10

예제

예제 1

입력

5 5 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 1 1 1 1

출력

3

예제 2

입력

5 5 1
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 1 1 1 1
0 0 0 0 0

출력

3

예제 3

입력

5 5 2
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
1 1 1 1 1
0 0 0 0 0

출력

5

예제 4

입력

5 5 5
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1
1 1 1 1 1

출력

15

예제 5

입력

6 5 1
1 0 1 0 1
0 1 0 1 0
1 1 0 0 0
0 0 0 1 1
1 1 0 1 1
0 0 1 0 0

출력

9

예제 6

입력

6 5 2
1 0 1 0 1
0 1 0 1 0
1 1 0 0 0
0 0 0 1 1
1 1 0 1 1
0 0 1 0 0

출력

14

My Sol

def archor(i, s):
    global archors, used, W, D, H, Hdec
    if i==3:           # 궁수 3자리 선택 하면 
        War(archors)   # War() 시작
        Hdec = H       # War 이후 Hdec 초기화
        return

    for k in range(s, W):
        if not used[k]:
            used[k] = 1
            archors.append(k)
            archor(i+1, k+1)
            used[k] = 0
            archors.pop()


def War(archors):
    global mat, Hdec, matdec, max_kill

    # mat으로부터 matdec 생성
    matdec = []                            
    for lst in mat:
        matdec.append(lst[::])

    # 한 wave마다 sum_kill 누적
    sum_kill = 0
    while Hdec > 0:
        setArchors(archors)            # matdec에 배치대로 궁수 배치
        sum_kill += attack(archors)    # 한 wave 마무리한 공격 수인 attack() 함수 반환값을 sum_kill 에 누적
        matdec.pop()                   # 궁수 배치 빼고
        matdec.pop()                   # 적들은 한 칸 내려옴
        Hdec -= 1                      # 최하단 행 인덱스인 Hdec 1 감소

    # 현재 최고 공격수와 이번 배치의 누적 공격수 비교해 최댓값을 max_kill에 저장
    max_kill = max(max_kill, sum_kill)


def setArchors(archors):
    global W, matdec

    # 성은 2로 두고 궁수의 위치는 3으로 두어 matdec에 추가
    lst = [2]*W
    for archor in archors:
        lst[archor] = 3
    matdec.append(lst)


def attack(archors):
    global matdec
    global D
    attack_lst = []

    # 궁수별 최적의 적 좌표 반환값을 attack_lst에 저장
    for archor in archors:
        # 이번 궁수의 최적의 적 좌표 리스트 반환값을 attackXY에 저장
        attackXY = selectEnemy(archor, D)
        
        # 이번 궁수 범위 내 적 없으면 다음 궁수 조회
        if not attackXY:  
            continue
        
        # attack_lst에 같은 적 좌표가 없으면 적 좌표 추가
        if not attackXY in attack_lst:
            attack_lst.append(attackXY)

    # 적 좌표 리스트 각각 조회해 적 제거 후 숫자 세고 이를 반환
    attackCnt = 0
    for attack in attack_lst:
        ai, aj = attack
        matdec[ai][aj] = 0
        attackCnt += 1

    return attackCnt


# 궁수마다 최적의 적을 선택하여 좌표를 반환하는 함수
def selectEnemy(archor, D):
    global Hdec, W

    # x, y 좌표와 궁수로부터의 거리를 담은 Queue 이용
    areaQ = [(Hdec, archor, 0)]
    start = -1
    end = 1
    visited = [[0]*W for _ in range(Hdec+1)]

    while start < end-1:
        start += 1
        ni, nj, dis = areaQ[start]        # Queue의 특정 좌표 사용

        if dis == D:                      # 특정 좌표와 궁수까지의 거리가 D라면 이 좌표 주변 탐색 불가
            if matdec[ni][nj]==1:         # 이 좌표의 값이 1이라면 이 좌표를 반환하면 된다. (왼쪽부터 Queue에 저장)
                return ni, nj
            else:
                continue

        didj = [(0,-1), (-1,0), (0,1)]                     # 좌상우 순으로 조회
        for di, dj in didj:
            if 0<=ni+di and 0<=nj+dj<W:                    # 범위를 벗어나지 않고
                if matdec[ni+di][nj+dj]==1:                # 주변 탐색값이 1이라면 바로 해당 좌표 반환
                    return ni+di, nj+dj

                if not visited[ni+di][nj+dj]:              # 확인하지 않았던 곳이라면
                    visited[ni+di][nj+dj] = 1              # 해당 좌표를 확인했다고 체크
                    areaQ.append((ni+di, nj+dj, dis+1))    # 현재 좌표거리에서 거리를 1 추가하고 좌표와 함께 areaQ에 삽입
                    end += 1

H, W, D = map(int, input().split())
mat = [list(map(int, input().split())) for _ in range(H)]
Hdec = H
matdec = []

archors = []
used = [0]*W
enemies = []
max_kill = 0
archor(0, 0)

print(max_kill)

공격할 대상을 선택하는 것도, 그리고 모든 궁수가 한 번에 공격을 해야하는 것도, 적이 내려오기 때문에 mat 자체를 바꿔줘야하는 것도 꽤나 까다로운 문제였다. 함수를 나누어 모듈화하였고, 코드가 많기 때문에 자잘한 실수도 주의해야 했다.

3명의 궁수를 선택하여 배치하는 모든 경우의 수를 따지므로 완전탐색과 백트래킹을 사용하고, 이 궁수를 선택할 때에는 DFS와 조합, 재귀함수를 사용한다. 궁수마다 최적의 적 좌표를 계산하는 selectEnemy() 함수에서는 BFS를 사용하여 가장 가까운 거리이면서 왼쪽에 있는 적의 좌표를 반환한다.

각 코드별 설명을 하위에 하기에는 코드가 너무 길어서 작성한 코드마다 주석으로 설명을 달겠다.

결과

맞았습니다!!