코드트리 - 포탑 부수기 (Python)

import sys
from collections import deque

# Solution
class Turret:
    def __init__(self, idx, x, y, attk):
        self.idx = idx
        self.x = x
        self.y = y
        self.attk = attk
        self.time = 0

    def __lt__(self, other):
        self_sum = self.x + self.y
        other_sum = other.x + other.y
        return (self.attk, -self.time, -self_sum, -self.y) < (other.attk, -other.time, -other_sum, -other.y)

    def __repr__(self):
        return f"{self.attk}"

# Step 1: 공격자, 대상자 선정
def get_attacker_and_target(t):
    sorted_list = sorted(turret_dict.items(), key=lambda x: x[1])

    _, attacker = sorted_list[0]
    _, target = sorted_list[-1]

    attacker.attk += N + M
    attacker.time = t

    return attacker, target

# Step 2: 공격
def attack(attacker, target):
    is_success, path = laser(attacker, target)

    if not is_success:
        path = bomb(attacker, target)

    return path

# Step 2-1: 레이저 공격
def laser(attacker, target):
    dq = deque()
    dq.append([attacker.x, attacker.y, []])
    visited = [[False] * M for _ in range(N)]

    while dq:
        x, y, path = dq.popleft()
        for dx, dy in dirs:
            nx = (x + dx) % N
            ny = (y + dy) % M

            if not visited[nx][ny] and turret_map[nx][ny] != 0:
                if nx == target.x and ny == target.y:
                    path.append(target.idx)
                    return True, path
                dq.append([nx, ny, path + [turret_map[nx][ny]]])
                visited[nx][ny] = True

    return False, []

# Step 2-2: 폭탄 공격
def bomb(attacker, target):
    path = []
    x, y = target.x, target.y

    for dx in range(-1, 2, 1):
        for dy in range(-1, 2, 1):
            nx = (x + dx) % N
            ny = (y + dy) % M
            if turret_map[nx][ny] != 0 and turret_map[nx][ny] != attacker.idx:
                path.append(turret_map[nx][ny])

    return path

# Step 3: 데미지 계산 (path: attk // 2, target: attk)
# Step 4: 포탑 정비 (공격에 기여하지 않은 포탑들)
def get_damage_and_recovery(attacker, target, path):
    broken_turret = []
    for tid, turret in turret_dict.items():
        if turret == attacker:
            continue

        if tid in path:
            if turret == target:
                damage = attacker.attk
            else:
                damage = attacker.attk // 2

            turret.attk -= damage
            if turret.attk <= 0:
                broken_turret.append(tid)

        else:
            turret.attk += 1

    for tid in broken_turret:
        turret = turret_dict[tid]
        turret_map[turret.x][turret.y] = 0
        del turret_dict[tid]

# Main
N, M, K = map(int, sys.stdin.readline().split())
turret_dict = {}
turret_map = [[0] * M for _ in range(N)]
dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]

# get turret data
idx = 1
for i in range(N):
    row = list(map(int, sys.stdin.readline().split()))
    for j in range(M):
        if row[j] > 0:
            turret = Turret(idx, i, j, row[j])
            turret_map[i][j] = turret.idx
            turret_dict[idx] = turret
            idx += 1

# game
for i in range(1, K + 1):
    attacker, target = get_attacker_and_target(i)
    path = attack(attacker, target)
    get_damage_and_recovery(attacker, target, path)
    if len(turret_dict) == 1:
        break

answer = 0
for t in turret_dict.values():
    answer = max(answer, t.attk)

print(answer)
ㄴ