백준-17135-캐슬 디펜스

문제

캐슬 디펜스

풀이

문제조건 해석

게임 구현 문제다.

문제를 제대로 이해하는 것이 중요하다.

• 최대한 많은 적을 죽이는 경우가 정답이다.
  • 궁수의 위치에 따라 적을 죽이는 수가 달라짐
    • 궁수 위치에 대한 경우의 수를 구해야 함
• 죽일 적은 거리가 가까운 순서대로 찾는다.

알고리즘

• 궁수 위치에 따른 경우의 수는 조합으로 찾는다.
• 죽일 적은 BFS를 통해 가까운 적부터 찾는다.

코드

from sys import stdin
from itertools import combinations
from copy import deepcopy

input = stdin.readline

n, m, d = [int(x) for x in input().rstrip().split()]
maps = []
for _ in range(n):
  maps.append([int(x) for x in input().rstrip().split()])

def kill_nearest_target(r, c, d, maps):
  '''
  BFS로 가장 가까운 타깃 찾는다
  '''
  # 궁수 바로 앞 위치
  queue = [(r-1, c)]
  level = 1
  # 사거리 범위 동안
  while queue and level <= d:
    for _ in range(len(queue)):
      rr, cc = queue.pop(0)
      if maps[rr][cc]: # 적이 있으면
        return (rr, cc)
      # 같은 거리일 때 가장 왼쪽부터 push
      if cc > 0:
        queue.append((rr, cc-1))
      if rr > 0:
        queue.append((rr-1, cc))
      if cc < m-1:
        queue.append((rr, cc+1))
    level += 1
  return False
    

def game(archeries, maps):
  total_kill = 0
  # 궁수의 row 위치를 한칸씩 위로 올리며 진행
  for archery_row in range(n, 0, -1):
    # 궁수가 같은 적에게 활을 쏠 수 있다.
    tmp_kill = set()
    for archery_col in archeries:
      target = kill_nearest_target(archery_row, archery_col, d, maps)
        if target:
          tmp_kill.add(target)
    total_kill += len(tmp_kill)
    for r, c in tmp_kill:
      # 적 죽음 처리
      maps[r][c] = 0
  return total_kill
        

# 궁수를 배치하는 경우의 수별로 kill 수 구한 후 최댓값 구한다
print(max(game(archery, deepcopy(maps)) for archery in combinations(range(m), 3)))

배운점

• 구현 문제는 문제를 제대로 이해하는 것이 중요하다.
  • 같은 적 쏠 수 있다는 조건 이해하지 못함.
• 디버깅 시간이 너무 오래 걸렸다.
  • 최초 코드 작성시부터 버그 고려하면서 작성하자