[코드트리 | 삼성] 포탑 부수기

문제 개요

• 공격자
  • 가장 약한 포탑
    • 가장 낮은 공격력
    • 가장 최근에 공격
    • 행과 열의 합이 큰 포탑
    • 열 값이 큰 포탑 순으로 선정
  • 공격력이 전체 행+전체 열만큼 늘어남
• 타겟 포탑
  • 가장 강한 포탑
    • 가장 높은 공격력
    • 가장 예전에 공격
    • 행과 열의 합이 작은 포탑
    • 열 값이 작은 포탑
  • 공격자 선정 기준의 반대
• 공격
  • 레이저 공격
    • 상하좌우 4개 방향
    • 포탑이 있는 경로로만 이동
    • 가장자리에서 반대쪽으로 나옴
    • 우 하 좌 상 순서로 경로 결정
    • 경로에 있는 포탑은 공격력//2 만큼 감소, 타겟은 공격력 만큼 감소
  • 포탄 공격
    • 공격 대상은 공격력만큼 감소, 그 주변 8방향 내의 포탑은 공격력//2만큼 감소
    • 가장자리에 포탄이 떨어지면 반대편 격자에 영향을 미침
• 포탑 부서짐
  • 공격력 0 이하이면 포탑이 부서짐
• 포탑 정비
  • 공격 이후, 부서지지 않은 포탑 중 공격자/공격 경로에 있던 포탑/공격 타겟 포탑이 아니였던 포탑은 공격력이 1씩 증가

문제를 위와 같이 정리할 수 있다.

풀이과정, 방향

공격자/타겟 지정 함수와 레이저 공격, 포탄 공격 함수를 각각 만들기
언제 공격했는지 기록하는 리스트 만들어서 공격자/타겟 지정할때 사용하기

유의점

공격자 선정 후, 공격력을 바로 올리면 타겟에 중복 선정이 되는 경우가 있으므로 공격자를 따로 제외하거나 이후에 처리하도록 해야 한다.
가장자리를 넘어서는 공격은 모듈러 연산으로 처리한다.

코드

from collections import deque

n, m, k = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]

tower_attack = [[-1]*m for _ in range(n)]
attacker = [0,0]
defencer = [0,0]


def attack():
    global arr, tower_attack, attacker
    power = 5001
    ay, ax = attacker
    for i in range(n):
        for j in range(m):
            if arr[i][j]>0:
                if arr[i][j] < power:
                    ay, ax = i,j
                    power = arr[i][j]
                elif arr[i][j] == power:
                    if tower_attack[i][j] > tower_attack[ay][ax]:
                        ay, ax = i,j
                        # power = arr[i][j]
                    elif tower_attack[i][j] == tower_attack[ay][ax]:
                        if i+j > ay+ax:
                            ay, ax = i,j
                            # power = arr[i][j]
                        elif i+j == ay+ax:
                            if j > ax:
                                ay, ax = i,j
    attacker = [ay, ax]

def defence():
    global arr, attacker, tower_attack, defencer
    power = 0
    ay, ax = attacker
    by, bx = defencer

    for i in range(n):
        for j in range(m):
            if i==ay and j==ax: continue
            if arr[i][j] > 0:
                if arr[i][j] > power:
                    by, bx = i,j
                    power = arr[i][j]
                elif arr[i][j]==power:
                    if tower_attack[i][j] < tower_attack[by][bx]:
                        by, bx = i,j
                        # power = arr[i][j]
                    elif tower_attack[i][j] == tower_attack[by][bx]:
                        if i+j < by+bx:
                            by, bx = i,j
                            # power = arr[i][j]
                        elif i+j == by+bx:
                            if j < bx:
                                by, bx = i,j
                                # power = arr[i][j]
    defencer = [by, bx]


def laser_attack():
    global arr, attacker, defencer, attack

    ay, ax = attacker
    by, bx = defencer

    q = deque()
    q.append([ay, ax,[]])

    dy = [0, 1, 0, -1]
    dx = [1, 0, -1, 0]
    visited = [[0] * m for i in range(n)]
    visited[ay][ax]=1
    while q:
        cy, cx, route = q.popleft()

        for i in range(4):
            ny = (cy + dy[i])%n
            nx = (cx + dx[i])%m

            if visited[ny][nx]==1: continue
            if arr[ny][nx]==0: continue

            if ny==by and nx == bx:
                arr[ny][nx]-=arr[ay][ax]
                for ry, rx in route:
                    arr[ry][rx] -= (arr[ay][ax])//2
                    attacked[ry][rx] = True
                return True

            tmp_route = route[:]
            tmp_route.append((ny, nx))
            visited[ny][nx]=1
            q.append([ny, nx, tmp_route])

    return False

def canon_attack():
    global arr, attacker, defencer, attacked
    ay, ax = attacker
    by, bx = defencer

    for i in range(by-1, by+2):
        for j in range(bx-1, bx+2):
            ny = i%n
            nx = j%m
            if ny==ay and nx==ax: continue
            if ny==by and nx==bx:
                arr[ny][nx]-=arr[ay][ax]
            else:
                arr[ny][nx]-=arr[ay][ax]//2
                attacked[ny][nx] = True

def fix():
    global arr, attacked, attacker, defencer
    cnt = 0
    for i in range(n):
        for j in range(m):
            if arr[i][j]<0:
                arr[i][j]=0
            elif arr[i][j]>0:
                cnt+=1
                if attacked[i][j]: continue
                else:
                    arr[i][j]+=1
    if cnt <= 1:
        return True
    else:
        return False

def find_max():
    global arr
    max_val = 0
    for a in arr:
        max_val = max(max_val, max(a))
    return max_val


for i in range(k):
    attack()
    defence()
    attacked = [[False]*m for i in range(n)]


    ay, ax = attacker
    by, bx = defencer
    attacked[ay][ax]=True
    attacked[by][bx]=True

    arr[ay][ax]+=m+n
    tower_attack[ay][ax]=i
    if not laser_attack():
        canon_attack()

    if fix():
        break

answer= find_max()
print(answer)

느낀점

공격자/타겟 선정의 기준이 반대여서 애매하게 sort로 처리하려다 더 복잡해질 뻔했다. 역시 삼성 구현에서는 if문을 사용하는 게 맞다.
공격자 선정 후 공격력 높이고 타겟 선정하려 하면 공격자==타겟이 되는 경우가 있어서 아예 따로 조건을 주거나 선정 다 한 이후에 공격력을 높여야 했다. 이 부분 다 출력하고서야 깨달았다...
중간에 공격력을 M, N이 아닌 그 칸의 행/열의 합만큼 높여서 잘못 풀었는데, 문제를 좀 더 꼼꼼히 읽을 필요를 느꼈다.