🥚문제

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

• 구현
• 그래프 이론
• 브루트포스 알고리즘
• 시뮬레이션

---

🥚입력/출력

---

🍳코드

import sys
from itertools import combinations
from copy import deepcopy
input = sys.stdin.readline


def dist(r1, c1, r2, c2):
    return abs(r1 - r2) + abs(c1 - c2)


def attack(game, archers, enemies):
    new_game = deepcopy(game)
    # 제거한 적 수를 구하기 위한 집합 (같은 적을 두번 죽였을 때 2로 카운트하지 않기 위해)
    # killed에 제거한 적의 좌표 (r, c)를 추가한다.
    killed = set()
    for archer in archers:
        targets = []  # 공격 가능한 적의 정보 저장 (거리, 행, 열)
        for enemy in enemies:
            r, c = enemy
            if dist(N, archer, r, c) <= D:
                targets.append((dist(N, archer, r, c), r, c))

        # 공격할 수 있는 적이 없는 경우
        if len(targets) == 0:
            continue

        # 현 archer가 공격할 적은 가장 가까운 적이고, 가장 왼쪽에 있는 적
        # 거리를 1순위, 열을 2순위로 targets를 정렬한다
        targets = sorted(targets, key=lambda x: (x[0], x[2]))
        # 최종 공격 적
        target = targets[0]
        new_game[target[1]][target[2]] = 0
        # 제거한 적 수 증가
        killed.add((target[1], target[2]))

    # 제거한 적 수와, 적을 제거한 뒤의 게임판 반환
    return len(killed), new_game


def get_enemies(arr):
    enemies = []
    for r in range(N):
        for c in range(M):
            if arr[r][c] == 1:
                enemies.append((r, c))
    return enemies


N, M, D = map(int, input().split())
# 0 = 빈칸, 1 = 적
arr = [list(map(int, input().split())) for _ in range(N)] + [[0]*M]

# 궁수를 배치하는 경우의 수는 mC3
archer_combis = list(combinations(list(range(M)), 3))

# 궁수의 공격으로 제거할 수 있는 적의 최대 수
answer = 0

for archers in archer_combis:
    # 궁수를 archer 조합으로 배치한 경우의 게임 판
    game = deepcopy(arr)
    # 현 조합으로 궁수를 배치한 경우, 제거할 수 있는 적의 수
    total_cnt = 0
    # 적이 있는 위치 저장
    enemies = get_enemies(game)
    # 게임판 내에 적이 있을 때까지 게임 진행
    while enemies:
        cnt, new_game = attack(game, archers, enemies)
        total_cnt += cnt
        # 적 아래로 이동
        game = [[0]*M]
        for i in range(N-1):
            game += [new_game[i]]
        game += [[0]*M]
        # enemies 업데이트
        enemies = get_enemies(game)

    answer = max(answer, total_cnt)

print(answer)

---

🧂아이디어

구현

• 각 턴마다 해야할 일
  • 궁수를 배치한다
  • 모든 궁수가 각각 적 하나를 공격한다
    : 공격은 거리가 D이하인 적 중 가장 가까운 적을 하고,
    공격할 수 있는 적이 여러명이라면 가장 왼쪽 적을 공격한다
  • 적이 한 칸 아래로 이동한다
• 모든 적이 N*M 게임판을 벗어나면 끝난다.

---

1. 격자판 행의 수 N, 열의 수 M, 궁수의 공격 거리 제한 D 및 격자판의 상태 arr를 입력 받는다.

2. 3명의 궁수를 배치할 수 있는 조합을 구한 뒤 리스트 형태로 archer_combis에 저장한다.
   궁수들을 배치할 수 있는 열인 [0, 1, ... , M-1] 원소들 중 3개 조합을 구하면 된다.
   itertools라이브러리의 combinations함수를 이용하여 간단하게 구할 수 있다.

3. archer_combis에 저장되어 있는 가능한 조합 별로 궁수를 배치해보고 제거할 수 있는 적의 최대 수를 갱신해간다.
   archer_combis의 조합 중 시도해볼 조합을 archers라고 하고 아래 설명을 이어가자.
   ("각 턴마다 해야할 일" 중 "궁수를 배치한다" 완료✅)

4. 궁수를 archers 조합으로 배치하고 게임을 하는 경우, 게임을 진행할 판을 game이라고 한다. game은 격자판의 상태인 arr을 deepcopy한 것이다.

5. 턴을 진행하기 전,
   현 조합으로 게임을 진행할 때 제거할 수 있는 적의 수를 저장하는 변수 total_cnt와,
   현재 게임판인 game에서 적이 있는 좌표를 저장하는 리스트 enemies를 초기화한다.

6. 턴은 게임판 내에 적이 존재하는 이상 계속 진행된다.
   먼저, 배치된 궁수들이 적을 공격하고 제거한 적 수와, 적을 제거한 뒤의 게임판 상태를 리턴하는 함수 attack(game, archers, enemies)를 호출한다.

• 🔽 attak 함수 내의 주요 내용들 🔽
• ✨ 제거한 적의 수를 구하기 위해 집합 자료형을 사용하였다.
  문제 설명에 따르면, 다른 궁수가 같은 적을 동시에 죽일 수가 있다.
  이때, 같은 적을 두 번 죽일 때 2로 카운트하지 않기 위해 집합 자료형을 사용한다.
  적을 죽일 때마다 그 좌표를 집합 자료형에 add한다면, 마지막에 집합 자료형의 길이가 죽인 적의 수가 된다.
• ✨ 또한, 한 궁수가 공격할 수 있는 적은 1순위가 거리가 가장 가까운 적이고 2순위가 가장 왼쪽에 있는 적이다. 따라서 한 궁수가 죽일 수 있는 적들을 (거리, 행, 열)의 튜플 자료형으로 한 리스트 내에 저장해두고 sorted함수를 통해 거리를 1순위, 열을 2순위로 정렬하면 최종 공격할 적을 쉽게 구할 수 있다.
  ("각 턴마다 해야할 일" 중 "모든 궁수가 각각 적 하나를 공격한다" 완료✅)

7. attack함수를 통해 얻은 cnt(이번 턴에 제거한 적 수)를 total_cnt(현 조합으로 궁수를 배치한 경우 제거 가능한 적 수)에 더한다.

8. 적을 한 행씩 아래로 이동시킨다. 이후, 적이 있는 좌표를 저장하는 리스트인 enemies를 업데이트한다.
   ("각 턴마다 해야할 일" 중 "적이 한 칸 아래로 이동한다" 완료✅)

9. 턴을 반복하다가, enemies의 길이가 0이 되면 중단한다.

10. 모든 조합을 시도해봤을 때, 궁수의 공격으로 제거할 수 있는 적의 최대 수를 저장하는 변수 answer를 갱신한다. answer = max(answer, total_cnt)

---

• 복잡하긴 하지만 충실히 구현하면 쉽게 풀 수 있었던 문제이다.

• 궁수를 배치하는 조합을 itertools의 combinations를 통해 편리하게 구할 수 있었다.

• attack함수를 구현하는 것을 조금 신경썼어야 하는데, 동시에 같은 적을 죽이는 경우에도 카운트를 1로 유지하기 위해 집합 자료형을 쓴다거나, multiple 조건으로 sort하는 것은 언제나 쓰일 수 있으니 기억해두자.