[CodeTree] 포탑 부수기 - 삼성 SW 역량테스트 2023 상반기 오전 1번 문제

 

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

 

문제 분석

• NxM 격자 위 모든 좌표에 포탑이 존재함.
• 각 포탑에는 공격력이 존재하고, 줄어들거나 늘어날 수 있으며 0이 되면 해당 포탑은 부숴져 더이상 공격/이동하지 못하게 됨.
• K턴 동안 공격자 선정 -> 공격 -> 포탑 부숴짐 및 정비 과정을 반복적으로 수행하며, 남은 포탑이 1개일 경우 그 즉시 게임을 종료.
• 공격자 선정
  • 부서지지 않은 포탑 중 가장 약한 포탑이 공격자로 선정되며, 약한 포탑은 N+M만큼의 공격력을 얻은 후 공격을 수행함.
  • (공격력이 낮은, 가장 최근에 공격한 포탑이, 행+열의 합이 큰, 열이 큰) 순서대로 우선순위를 가져 공격자를 선정함.
• 공격
  • 공격은 약한 포탑 -> 가장 강한 포탑을 공격하며, 가장 강한 포탑은 약한 포탑 우선순위의 반대임
  • 가능한 공격은 레이저 공격과 포탄 공격이며, 레이저 공격을 진행하지 못할 경우 포탄 공격을 수행함.
• 레이저 공격
  • 상하좌우 4방향으로 이동할 수 있으며, 범위를 넘어가게 되면 반대편으로 이어짐 (0, 0) -> (N-1, 0).
  • 부서진 포탑이 있는 위치는 이동할 수 없음.
  • 약한 포탑 -> 강한 포탑으로 가는 최단 거리로 공격을 수행함.
  • 최단 거리가 여러개 일 경우, 우/하/좌/상 우선순위대로 먼저 움직여 도착한 경로가 최단 거리가 됨.
  • 최단거리 내 좌표들은 (공격자의 공격력 //2)만큼 피해를 입고, 가장 강한 포탑은 (공격자의 공격력) 만큼 피해를 입음.
• 포탄 공격
  • 레이저 공격이 실패했을 경우, 공격 대상에 포탄을 던짐.
  • 포탄은 공격 대상 기준으로 상하좌우 + 대각선 방향으로 공격을 수행하며, 공격자는 피해를 입지 않음.
  • 8방향은 (공격자의 공격력 //2)만큼 피해를 입고, 가장 강한 포탑은 (공격자의 공격력) 만큼 피해를 입음.
• 부서짐 및 정비
  • 0이하가 된 포탑은 더이상 공격/이동을 수행하지 못하는 부서진 상태가 됨.
  • 공격이 끝난 후에, 공격 가능한 포탑 중 이번 턴에 공격과 무관했던 포탑은 공격력이 1씩 증가.
• 위 과정을 K번 반복하여 수행한 후, 가장 강한 포탑의 공격력을 Return하는 문제.

 

문제 접근

• 초기화 단계
  • 8방향 이동과 최근 언제 공격했는지를 O(1)로 판단하기 위한 초기 배열 선언.
• 공격자 선정
  • find_attacker() 함수로 구현했으며, NxM 배열을 순회하며 0이상의 포탑 정보를 _candits()에 추가.
  • 우선순위에 맞게 sort() 후, 공격자의 공격력을 N+M만큼 추가
• 레이저 공격
  • 공격자 포탑 좌표를 기준으로 BFS 순회하며 최단 거리를 탐색.
  • 우선순위에 맞게 4방향을 탐색하기 때문에, 가장 먼저 발견한 path가 우선순위에 맞는 최단거리임을 보장.
  • path가 없을 경우 포탄 공격 수행
  • 있을 경우 공격 경로 및 강한 포탑의 공격력을 요구사항에 맞게 감소시킴.
• 포탄 공격
  • 강한 포탑 및 포탑의 좌표 기준 8방향으로 공격 수행.
  • 8방향 중 공격자가 위치할 경우, 공격하면 안됨. (최초 제출 시 틀리게 된 이유)
• 정비
  • 공격에 참여한 좌표를 배열로 입력받은 후, 0이상 좌표 중 공격에 참가하지 않은 포탑의 공격력을 1씩 증가.
• 매 공격마다 남은 포탑의 수를 체크하며, 1개의 포탑이 남았을 때 즉시 종료.

 

소스 코드

# define lib
from collections import deque

# set value from input
N, M, K = map(int, input().split())
field = [list(map(int, input().split())) for _ in range(N)]
direc = [(0, 1), (1, 0), (0, -1), (-1, 0), (-1, 1), (1, -1), (1, 1), (-1, -1)]
last_attack = [[0]*M for _ in range(N)]

# define functions
def find_attacker():
    _candits = []
    for i in range(N):
        for j in range(M):
            if field[i][j] == 0:
                continue
            _candits.append((field[i][j], last_attack[i][j], i, j)) # power, last_attack, r, c
    _candits.sort(key=lambda x: (x[0], -x[1], -(x[2]+x[3]), -x[3]))
    sx, sy, ex, ey = *_candits[0][2:], *_candits[-1][2:]
    field[sx][sy] += (N+M)
    return sx, sy, ex, ey

def lazer_attack(sx, sy, ex, ey):
    dq, path = deque([(sx, sy, [])]), None
    visit = [[False]*M for _ in range(N)]
    visit[sx][sy] = True

    while dq:
        cx, cy, cpath = dq.popleft()
        if (cx, cy) == (ex, ey):
            path = cpath
            break
        
        # search with priority
        for didx in range(4):
            nx, ny = (cx+direc[didx][0])%N, (cy+direc[didx][1])%M
            if visit[nx][ny] or field[nx][ny] == 0:
                continue
            visit[nx][ny] = True
            dq.append((nx, ny, cpath+[(nx, ny)]))

    if path is None:
        return False, []

    for px, py in path[:-1]:
        field[px][py] = max(0, field[px][py]-(field[sx][sy]//2))
    field[ex][ey] = max(0, field[ex][ey]-field[sx][sy])
    return True, path + [(sx, sy)]

def bomb_attack(sx, sy, ex, ey):
    path = [(ex, ey)]
    for didx in range(8):
        nx, ny = (ex+direc[didx][0])%N, (ey+direc[didx][1])%M
        if (nx, ny) == (sx, sy):
            continue
        field[nx][ny] = max(0, field[nx][ny]-(field[sx][sy]//2))
        path.append((nx, ny))
    field[ex][ey] = max(0, field[ex][ey]-field[sx][sy])
    return path + [(sx, sy)]

def heal(path):
    for i in range(N):
        for j in range(M):
            if field[i][j] == 0 or (i, j) in path:
                continue
            field[i][j] += 1

def check():
    cnt = 0
    for i in range(N):
        for j in range(M):
            if field[i][j] == 0:
                continue
            cnt += 1
    return cnt

time = 0
while time < K:
    sx, sy, ex, ey = find_attacker()
    flag, path = lazer_attack(sx, sy, ex, ey)
    if not flag:
        path = bomb_attack(sx, sy, ex, ey)

    if check() < 2:
        break
    time += 1
    heal(path)
    last_attack[sx][sy] = time
    
print(max([max(line) for line in field]))