[코드트리] 포탑 부수기

문제 링크

포탑 부수기

구현 방식

• 내 기준 메모리 제한이 조금 빡셌다
  • 처음에 attack_potab과 defense_potab을 구하는 과정에서 매 반복마다 list에 [공격력, 몇번째(k)에 공격했는 지, 행과 열의 합, 열 값] 형식으로 모든 포탑을 append하고 sort() 해주는 방식으로 구현하였다가, 그냥 attack_potab()과 defense_potab()이라는 함수를 구현해서 처리해주었다
  • 그리고 bfs에서 중복 노드를 적절하게 제거해주는 게 필요했다. visit 리스트와 path 변수를 둘 다 활용하였다
• 레이저 공격을 처음엔 dfs로 구현했었는데, 계속 시간초과가 발생해서 bfs로 구현했더니 해결됐다. (왜 dfs로는 시간초과 해결이 안되는 지 잘 모르겠음)

코드

import sys
from collections import deque
import copy

#우 하 좌 상
dx = (0, 1, 0, -1)
dy = (1, 0, -1, 0)
pd = ((-1, -1), (-1, 0), (-1, 1), (0, -1), (0, 1), (1, -1), (1, 0), (1, 1))

N, M, K = map(int, sys.stdin.readline().strip().split())
board = [list(map(int, sys.stdin.readline().strip().split())) for n in range(N)]

potab_k = [[0 for m in range(M)] for n in range(N)]

def attack_potab():
    power = 5001
    ax, ay = 0, 0
    for i in range(N):
        for j in range(M):
            if board[i][j] == 0: continue
            if board[i][j] < power:
                power = board[i][j]
                ax, ay = i, j
            elif board[i][j] == power:
                if potab_k[i][j] > potab_k[ax][ay]:
                    ax, ay = i, j
                elif potab_k[i][j] == potab_k[ax][ay]:
                    if i+j > ax+ay: ax, ay = i, j
                    elif i+j == ax+ay:
                        if j > ay:
                            ay = j
    return ax, ay

def defense_potab(ax, ay):
    power = -1
    dx, dy = 0, 0
    for i in range(N):
        for j in range(M):
            if board[i][j] == 0: continue
            if (i, j) == (ax, ay): continue
            if board[i][j] > power:
                power = board[i][j]
                dx, dy = i, j
            elif board[i][j] == power:
                if potab_k[i][j] < potab_k[dx][dy]:
                    dx, dy = i, j
                elif potab_k[i][j] == potab_k[dx][dy]:
                    if i+j < dx+dy: dx, dy = i, j
                    elif i+j == dx+dy:
                        if j < dy:
                            dx, dy = i, j
    return dx, dy

for k in range(1, K+1):
    related = [[False]*M for n in range(N)] #공격과 관련있는 포탑

    ##### 공격자 선정
    a_x, a_y = attack_potab()
    potab_k[a_x][a_y] = k
    board[a_x][a_y] += N+M
    related[a_x][a_y] = True

    ##### 수비자 선정
    d_x, d_y = defense_potab(a_x, a_y)
    related[d_x][d_y] = True

    ##### 공격자의 공격
    flag = False #레이저 공격을 했는 지의 여부
    power = board[a_x][a_y]

    queue = deque([]); queue.append((a_x, a_y, [(a_x, a_y)]))
    visit = [[False]*M for n in range(N)]; visit[a_x][a_y] = True
    while queue:
        x, y, path = queue.popleft()

        if (x, y) == (d_x, d_y):
            flag = True
            board[d_x][d_y] -= power
            for i in range(len(path)-2, 0, -1): #path 추적
                board[path[i][0]][path[i][1]] -= power//2
                related[path[i][0]][path[i][1]] = True
            break

        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if nx == -1: nx = N-1
            if nx == N: nx = 0
            if ny == -1: ny = M-1
            if ny == M: ny = 0

            if not visit[nx][ny] and board[nx][ny] > 0 and (nx, ny) not in path:
                visit[nx][ny] = True
                queue.append((nx, ny, path+[(nx, ny)]))

    if not flag: #포탄 공격
        visit = [[False]*M for n in range(N)]; visit[d_x][d_y] = True
        for i in range(8):
            nx = d_x + pd[i][0]; ny = d_y + pd[i][1]

            if nx == -1: nx = N-1
            if nx == N: nx = 0
            if ny == -1: ny = M-1
            if ny == M: ny = 0

            if not visit[nx][ny] and (nx, ny) != (a_x, a_y):
                visit[nx][ny] = True
                board[nx][ny] -= power//2
                related[nx][ny] = True
        board[d_x][d_y] -= power

    ##### 포탑 부서짐
    for i in range(N):
        for j in range(M):
            if board[i][j] <= 0: board[i][j] = 0
            elif not related[i][j]: board[i][j] += 1

    # 포탑 하나 남으면 바로 종료
    cnt = 0
    for i in range(N):
        for j in range(M):
            if board[i][j] > 0: cnt += 1
    if cnt <= 1: break

answer = 0
for i in range(N):
    for j in range(M):
        answer = max(answer, board[i][j])
print(answer)