[백준 17135. 캐슬 디펜스]

youngtae·2023년 3월 29일

알고리즘 문제 풀이

목록 보기

8/12

문제

캐슬 디펜스는 성을 향해 몰려오는 적을 잡는 턴 방식의 게임이다. 게임이 진행되는 곳은 크기가 N×M인 격자판으로 나타낼 수 있다. 격자판은 1×1 크기의 칸으로 나누어져 있고, 각 칸에 포함된 적의 수는 최대 하나이다. 격자판의 N번행의 바로 아래(N+1번 행)의 모든 칸에는 성이 있다.

성을 적에게서 지키기 위해 궁수 3명을 배치하려고 한다. 궁수는 성이 있는 칸에 배치할 수 있고, 하나의 칸에는 최대 1명의 궁수만 있을 수 있다. 각각의 턴마다 궁수는 적 하나를 공격할 수 있고, 모든 궁수는 동시에 공격한다. 궁수가 공격하는 적은 거리가 D이하인 적 중에서 가장 가까운 적이고, 그러한 적이 여럿일 경우에는 가장 왼쪽에 있는 적을 공격한다. 같은 적이 여러 궁수에게 공격당할 수 있다. 공격받은 적은 게임에서 제외된다. 궁수의 공격이 끝나면, 적이 이동한다. 적은 아래로 한 칸 이동하며, 성이 있는 칸으로 이동한 경우에는 게임에서 제외된다. 모든 적이 격자판에서 제외되면 게임이 끝난다.

게임 설명에서 보다시피 궁수를 배치한 이후의 게임 진행은 정해져있다. 따라서, 이 게임은 궁수의 위치가 중요하다. 격자판의 상태가 주어졌을 때, 궁수의 공격으로 제거할 수 있는 적의 최대 수를 계산해보자.

격자판의 두 위치 (r1, c1), (r2, c2)의 거리는 |r1-r2| + |c1-c2|이다.

풀이

구현 내용이 까다로운 시뮬레이션 문제다.

구현 내용을 정리해보면
1. N+1번 행에 궁수 3명 배치
2. 각 턴마다 적이 있다면 궁수는 적 하나를 공격
3. 같은 거리에 있는 적이면 가장 왼쪽 적 공격
4. 턴이 끝나면 적들이 한 행씩 밑으로 이동

항목별로 함수를 만들어서 구현해주었다.
코드를 하나씩 살펴보면

궁수 3명 배치 조합 함수

# 궁수 3명 배치 조합
def comb(arr, n):
    result = []
    if n > len(arr):
        return result
    if n == 1:
        for i in arr:
            result.append([i])
    elif n > 1:
        for i in range(len(arr) - n + 1):
            for j in comb(arr[i + 1:], n - 1):
                result.append([arr[i]] + j)
    return result

itertools 라이브러리를 사용해도 되지만 삼성 기출 문제이기에 조합을 직접 구현해보았다.
n개의 원소를 가지는 부분집합을 구하는 것과 같다.
n이 1이 될 때까지 재귀 호출하며 각각의 부분집합을 구해서 합치는 형식이다.

적이 있는지 확인

# 적이 있는지 확인
def is_enemy(arr):
    for i in arr:
        if sum(i):
            return True
    else:
        return False

이 부분은 간단하게 각 행의 합이 0이 아니면 적이 있으므로 True를 반환해주었다.

턴이 끝나면 적이 한 행씩 이동

# 적이 한칸씩 이동
def move(arr):
    for i in range(N - 1, 0, -1):
        arr[i] = arr[i - 1]
    arr[0] = [0] * M

내림차순으로 가면서 위의 행을 아래 행에 대입했다.
가장 위에는 0 리스트를 추가했다.

디펜스

# 디펜스 시작
def attack():
    # 잡은 적 리스트
    kill = []
    catch = 0

    for a in arch:
        # 궁수별 잡을 수 있는 적
        enemy = []
        for j in range(N):
            for k in range(M):
                # 배열 돌면서 적 찾으면 거리 계산 후 사정거리 안이면 리스트 추가
                if tmp[j][k] == 1:
                    dis = abs(j - N) + abs(k-a[1])
                    if dis <= D:
                        enemy.append([dis, j, k])
        # 거리, 왼쪽 열 순으로 정렬
        enemy.sort(key=lambda x: (x[0], x[2]))
        # 가장 우선순위 높은 적 잡기
        if enemy:
            kill.append(enemy[0])

    # 잡은 적 0 처리하고 카운트
    for road, x, y in kill:
        if tmp[x][y] == 1:
            tmp[x][y] = 0
            catch += 1
    return catch

가장 핵심인 디펜스 내용이다.
1. 각 궁수마다 한명씩 공격하므로 조합을 통해 정한 각 좌표마다 탐색 진행
2. 배열 돌면서 적 찾으면 거리 계산 후 사정거리 이내면 거리와 함께 좌표를 공격가능 리스트에 추가
3. 배열을 다 돌면 우선순위대로 정렬 후 공격 가능한 적이 있다면 우선순위 가장 높은 적 공격
4. 나머지 궁수 2명도 똑같이 반복
5. 잡은 적은 0으로 처리하고 카운트, 여러 궁수가 같은 적을 공격할수도 있으므로 if문으로 공격처리

입력 및 실행

N, M, D = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
mx_cnt = 0
# 궁수 배치 좌표
pos = []
for i in range(M):
    pos.append([N, i])

# 궁수 3명 배치하는 경우의 수
for arch in comb(pos, 3):
    cnt = 0
    # 시뮬레이션 위해 배열 복사
    tmp = copy.deepcopy(arr)
    # 적이 있다면 공격
    while is_enemy(tmp):
        cnt += attack()
        move(tmp)
    mx_cnt = max(cnt, mx_cnt)

print(mx_cnt)

궁수들이 배치 가능한 좌표 리스트를 만들고 조합 함수 호출
시뮬레이션 위해 배열을 deepcopy로 복사
적이 있는 동안 계속 디펜스 진행
끝난 후 최댓값 출력

종합

# memory: 31832KB  time: 596ms (python)

import sys
import copy

input = sys.stdin.readline

# 궁수 3명 배치 조합
def comb(arr, n):
    result = []
    if n > len(arr):
        return result
    if n == 1:
        for i in arr:
            result.append([i])
    elif n > 1:
        for i in range(len(arr) - n + 1):
            for j in comb(arr[i + 1:], n - 1):
                result.append([arr[i]] + j)
    return result


# 적이 있는지 확인
def is_enemy(arr):
    for i in arr:
        if sum(i):
            return True
    else:
        return False


# 적이 한칸씩 이동
def move(arr):
    for i in range(N - 1, 0, -1):
        arr[i] = arr[i - 1]
    arr[0] = [0] * M


# 디펜스 시작
def attack():
    # 잡은 적 리스트
    kill = []
    catch = 0

    for a in arch:
        # 궁수별 잡을 수 있는 적
        enemy = []
        for j in range(N):
            for k in range(M):
                # 배열 돌면서 적 찾으면 거리 계산 후 사정거리 안이면 리스트 추가
                if tmp[j][k] == 1:
                    dis = abs(j - N) + abs(k-a[1])
                    if dis <= D:
                        enemy.append([dis, j, k])
        # 거리, 왼쪽 열 순으로 정렬
        enemy.sort(key=lambda x: (x[0], x[2]))
        # 가장 우선순위 높은 적 잡기
        if enemy:
            kill.append(enemy[0])

    # 잡은 적 0 처리하고 카운트
    for road, x, y in kill:
        if tmp[x][y] == 1:
            tmp[x][y] = 0
            catch += 1
    return catch


N, M, D = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(N)]
mx_cnt = 0
# 궁수 배치 좌표
pos = []
for i in range(M):
    pos.append([N, i])

# 궁수 3명 배치하는 경우의 수
for arch in comb(pos, 3):
    cnt = 0
    # 시뮬레이션 위해 배열 복사
    tmp = copy.deepcopy(arr)
    # 적이 있다면 공격
    while is_enemy(tmp):
        cnt += attack()
        move(tmp)
    mx_cnt = max(cnt, mx_cnt)

print(mx_cnt)