코드트리 - 포탑 부수기

문제

https://www.codetree.ai/training-field/frequent-problems/problems/destroy-the-turret/explanation?page=3&pageSize=5

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

 

 

N x M 격자가 있고, 모든 위치에는 포탑이 존재 한다. (즉, 포탑의 개수는 NM개)  각 포탑에는 공격력이 존재하고, 상황에 따라 공격력이 줄거나 늘수 있다. 0 이하가 된다면 , 포탑은 부서진다(공격기능 x)  

하나의 턴은 다음 4가지 액션을 순서대로 수형하며, 총 K번 반복한다.

 

1. 공격자 선정

부서지지 않은 포탑 중 가장 약한 포탑이 공격자로 선정됨.

공격자로 선정되면 해당 포탑의 공격력이 N + M 만큼 상승

가장 약한 포탑

• 공격력이 가장 낮은 포탑
• 공격력이 가장 낮은 포탑이 2개 이상이라면, 가장 최근에 공격한 포탑이 가장 약한 포탑(
  • 모든 포탑은 시점 0에 모두 공격한 경험이 있다고 가정.
• 만약 그러한 포탑이 2개 이상이라면, 각 포탑 위치의 행과 열의 합이 가장 큰 포탑
• 만약 그러한 포탑이 2개 이상이라면, 각 포탑 위치의 열 값이 가장 큰 포탑이 가장 약한 포탑

 

 

2. 공격자의 공격

1번에서 선정된 공격자는 자신을 제외한 가장 강한 포탑을 공격함.

가장 강한 포탑

• 공격력이 가장 높은 포탑
• 만약 공격력이 가장 높은 포탑이 2개 이상이라면, 공격한지 가장 오래된 포탑이 가장 강한 포탑
• 만약 그러한 포탑이 2개 이상이라면, 각 포탑 위치의 행과 열의 합이 가장 작은 포탑이 가장 강한 포탑
• 만약 그러한 포탑이 2개 이상이라면, 각 포탑 위치의 열 값이 가장 작은 포탑이 가장 강한 포탑.

 

공격 할 때에는 레이저 공격을 먼저 시도하고, 만약 그게 안된다면 포탄 공격

 

레이저 공격

레이저는 다음의 규칙으로 움직인다.

1. 상하좌우의 4개의 방향으로 움직일 수 있다.
2. 부서진 포탑이 있는 위치는 지날 수 없다.
3. 가장자리에서 막힌 방향으로 진행하고자 한다면, 반대편으로 나온다.
   • 예를 들어, 위의 예시에서 (2,3)에서 오른쪽으로 두번 이동한다면, (2,3) -> (2,4) -> (2,1) 순으로 이동합니다.

레이저 공격은 공격자의 위치에서 공격 대상 포탑까지의 최단 경로로 공격(우/하/좌/상 순)

그러한 경로가 존재하지 않는다면, 포탄 공격 진행

최단 경로가 정해졌으면, 공격 대상은 공격자의 공격력 만큼의 피해를 입히며, 해당 수치만큼 공격력이 낮아짐.

나머지 경로에 있는 포탑들은 공격자의 공격력의 절반 만큼의 공격을 받음

 

포탄 공격

공격 대상에 포탄을 던짐. 공격 대상은 공격자의 공격력 만큼의 피해를 받고, 해당 수치만큼 공격력이 낮아짐.

추가적으로 주위 8개의 방향에 있는 포탑도 피해를 입는데, 공격력의 절반만큼 피해를 받음(n//2)

공격자는 피해를 받지 않으며, 만약 가장자리에 포탄이 떨어졌다면, 위에서 레이저 이동처럼 포탄의 추가 피해가 반대편 격자에 미치게 됨.

위의 예시에서 공격자가 공격대상을 레이저로 공격

 

3. 포탑 부서짐

공격을 받아 공격력이 0이하가 된 포탑은 부서진다.

 

4. 포탑정비

공격이 끝났으면, 부서지지 않은 포탑 중 공격과 무관했던 포탑은 공격력이 1씩 올라간다.

공격과 무관하다는 뜻은 공격자도 아니고,공격에 피해를 입은 포탑도 아니란 뜻

k번의 턴이 끝나면 남은 포탑중 공격력이 가장 높은 포탑의 공격력을 출력

 

 

 

풀이

 

1. 입력 처리 및 초기 상태 설정

먼저 입력으로 주어지는 포탑 배열과 각 포탑의 상태를 읽어옵니다. 배열에서 각 포탑은 공격력으로 나타내어지고, 공격력이 0인 포탑은 이미 파괴된 상태로 간주합니다.

def read_input() -> Tuple[int, int, int, List[List[int]]]:
    """
    표준 입력으로부터 게임 설정과 초기 포탑 상태를 읽어옵니다.
    """
    n, m, k = map(int, sys.stdin.readline().split())
    arr = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
    return n, m, k, arr

 

 

2. 가장 약한 포탑 찾기

가장 약한 포탑을 찾기 위해서는 포탑의 공격력을 기준으로 정렬합니다. 만약 여러 포탑이 같은 공격력을 가지고 있다면, 마지막으로 공격한 시점이 가장 오래된 포탑을 선택하며, 그마저도 동일하다면 좌표의 우선순위를 따집니다.

def get_weak_tower(arr: List[List[int]], tower_last_attack: Dict[Tuple[int, int], int]) -> Tuple[int, int]:
    """
    가장 약한 포탑을 선정합니다.
    """
    n, m = len(arr), len(arr[0])
    weak_tower = []
    weak_attack = int(1e9)
    
    for i in range(n):
        for j in range(m):
            if arr[i][j] == 0:
                continue
            if arr[i][j] == weak_attack:
                weak_tower.append((i, j))
            elif arr[i][j] < weak_attack:
                weak_attack = arr[i][j]
                weak_tower = [(i, j)]

    # 추가 조건: 마지막 공격이 오래된 순으로 정렬
    ...
    return weak_tower_2[0]

 

 

3. 가장 강한 포탑 선정

공격자가 정해진 후에는 가장 강한 포탑을 찾아 공격합니다. 이때, 공격 대상이 될 포탑은 공격력이 가장 높은 포탑으로 선정되며, 여러 포탑이 동일한 공격력을 가지고 있을 경우 마지막 공격 시점이 가장 최근인 포탑을 선택합니다.

def get_target_tower(arr: List[List[int]], tower_last_attack: Dict[Tuple[int, int], int],
                     weak_tower: Tuple[int, int]) -> Tuple[int, int]:
    """
    가장 강한 포탑을 선정합니다.
    """
    n, m = len(arr), len(arr[0])
    strong_tower = 0
    target_tower = []
    
    for i in range(n):
        for j in range(m):
            if (i, j) == weak_tower or arr[i][j] == 0:
                continue
            if strong_tower == arr[i][j]:
                target_tower.append((i, j))
            elif strong_tower < arr[i][j]:
                strong_tower = arr[i][j]
                target_tower = [(i, j)]

    # 추가 조건: 마지막 공격이 최근인 순으로 정렬
    ...
    return strong_tower_2[0]

 

 

4. 레이저 공격 경로 탐색

레이저 공격은 최단 경로로 이루어지며, 이를 찾기 위해 BFS(너비 우선 탐색)를 사용합니다. 공격자는 목표 포탑까지의 경로를 찾고, 그 경로에 있는 포탑들에게 피해를 줍니다.

def get_razer_path(arr: List[List[int]], weak_tower: Tuple[int, int], target_tower: Tuple[int, int]) -> List[Tuple[int, int]]:
    """
    레이저 공격 경로를 찾습니다.
    """
    ...
    return path

 

 

5. 포탄 공격 경로 계산

레이저 공격이 불가능할 경우, 포탄 공격을 진행합니다. 포탄 공격은 목표 포탑과 그 인접한 포탑들에게 피해를 주며, 격자의 경계를 넘는 경우 반대편으로 이동하게 됩니다.

def get_bomb_path(arr: List[List[int]], target_tower: Tuple[int, int]) -> List[Tuple[int, int]]:
    """
    포탄 공격 경로를 계산합니다.
    """
    ...
    return path

 

 

 

코드

import sys
from collections import deque
from typing import List, Tuple, Dict


def read_input() -> Tuple[int, int, int, List[List[int]]]:
    """
    표준 입력으로부터 게임 설정과 초기 포탑 상태를 읽어옵니다.

    Returns:
        Tuple[int, int, int, List[List[int]]]: 행의 수, 열의 수, 턴 수, 초기 포탑 배열
    """
    n, m, k = map(int, sys.stdin.readline().split())
    arr = []
    for _ in range(n):
        arr.append(list(map(int, sys.stdin.readline().split())))

    return n, m, k, arr


def get_weak_tower(arr: List[List[int]], tower_last_attack: Dict[Tuple[int, int], int]) -> Tuple[int, int]:
    """
    가장 약한 포탑을 선정합니다.

    Args:
        arr (List[List[int]]): 현재 포탑 배열
        tower_last_attack (Dict[Tuple[int, int], int]): 각 포탑의 마지막 공격 턴

    Returns:
        Tuple[int, int]: 가장 약한 포탑의 좌표
    """
    n = len(arr)
    m = len(arr[0])

    weak_tower = []
    weak_attack = int(1e9)
    for i in range(n):
        for j in range(m):
            if arr[i][j] == 0:
                continue
            if arr[i][j] == weak_attack:
                weak_tower.append((i, j))
            elif arr[i][j] < weak_attack:
                weak_attack = arr[i][j]
                weak_tower = [(i, j)]

    if len(weak_tower) == 1:
        return weak_tower[0]

    last_attack = 0
    weak_tower_2 = []
    for (i, j) in weak_tower:
        if tower_last_attack[(i, j)] == last_attack:
            weak_tower_2.append((i, j))
        elif tower_last_attack[(i, j)] > last_attack:
            weak_tower_2 = [(i, j)]
            last_attack = tower_last_attack[(i, j)]

    weak_tower_2 = sorted(weak_tower_2, key=lambda x: (-(x[0] + x[1]), -x[1]))

    return weak_tower_2[0]


def get_target_tower(arr: List[List[int]], tower_last_attack: Dict[Tuple[int, int], int],
                     weak_tower: Tuple[int, int]) -> Tuple[int, int]:
    """
    가장 강한 포탑(공격 대상)을 선정합니다.

    Args:
        arr (List[List[int]]): 현재 포탑 배열
        tower_last_attack (Dict[Tuple[int, int], int]): 각 포탑의 마지막 공격 턴
        weak_tower (Tuple[int, int]): 가장 약한 포탑의 좌표

    Returns:
        Tuple[int, int]: 가장 강한 포탑의 좌표
    """
    n = len(arr)
    m = len(arr[0])

    target_tower = []
    strong_tower = 0

    for i in range(n):
        for j in range(m):
            if (i, j) == weak_tower or arr[i][j] == 0:
                continue
            if strong_tower == arr[i][j]:
                target_tower.append((i, j))
            elif strong_tower < arr[i][j]:
                strong_tower = arr[i][j]
                target_tower = [(i, j)]

    if len(target_tower) == 1:
        return target_tower[0]

    last_attack = int(1e9)
    strong_tower_2 = []
    for (i, j) in target_tower:
        if tower_last_attack[(i, j)] == last_attack:
            strong_tower_2.append((i, j))
        elif tower_last_attack[(i, j)] < last_attack:
            strong_tower_2 = [(i, j)]
            last_attack = tower_last_attack[(i, j)]

    strong_tower_2 = sorted(strong_tower_2, key=lambda x: (x[0] + x[1], x[1]))
    if len(strong_tower_2) == 0:
        return ''
    return strong_tower_2[0]


def get_razer_path(arr: List[List[int]], weak_tower: Tuple[int, int], target_tower: Tuple[int, int]) -> List[Tuple[int, int]]:
    """
    레이저 공격 경로를 찾습니다.

    Args:
        arr (List[List[int]]): 현재 포탑 배열
        weak_tower (Tuple[int, int]): 공격하는 포탑의 좌표
        target_tower (Tuple[int, int]): 공격 대상 포탑의 좌표

    Returns:
        List[Tuple[int, int]]: 레이저 공격 경로
    """
    dx = [1, 0, -1, 0]
    dy = [0, 1, 0, -1]

    n = len(arr)
    m = len(arr[0])
    visited = [[0] * m for _ in range(n)]

    q = deque()
    q.append((weak_tower[0], weak_tower[1], []))
    visited[weak_tower[0]][weak_tower[1]] = 1

    while q:
        y, x, path = q.popleft()
        if (y, x) == target_tower:
            return path
        for d in range(4):
            ny = y + dy[d]
            nx = x + dx[d]

            # 격자 밖으로 나가면 반대로가기
            if ny == n:
                ny = 0
            elif nx == m:
                nx = 0
            elif ny < 0:
                ny = n - 1
            elif nx < 0:
                nx = m - 1

            if arr[ny][nx] > 0 and visited[ny][nx] == 0:
                visited[ny][nx] = 1
                q.append((ny, nx, path + [(ny, nx)]))

    return []


def get_bomb_path(arr: List[List[int]], target_tower: Tuple[int, int]) -> List[Tuple[int, int]]:
    """
    포탄 공격 경로를 찾습니다.

    Args:
        arr (List[List[int]]): 현재 포탑 배열
        target_tower (Tuple[int, int]): 공격 대상 포탑의 좌표

    Returns:
        List[Tuple[int, int]]: 포탄 공격 영향을 받는 좌표 목록
    """
    dx = [1, 1, 1, -1, -1, -1, 0, 0]
    dy = [1, -1, 0, 1, -1, 0, 1, -1]

    y, x = target_tower
    n = len(arr)
    m = len(arr[0])
    path = []
    for d in range(8):
        ny = y + dy[d]
        nx = x + dx[d]

        if ny == n:
            ny = 0
        elif ny < 0:
            ny = n - 1

        if nx == m:
            nx = 0
        elif nx < 0:
            nx = m - 1

        path.append((ny, nx))
    return path


def main():
    """
    메인 함수: 게임 로직을 실행합니다.
    """
    n, m, k, arr = read_input()
    tower_last_attack: Dict[Tuple[int, int], int] = {}

    for i in range(n):
        for j in range(m):
            tower_last_attack[(i, j)] = 0

    for t in range(k):
        # 가장 약한 포탑 선정
        weak_tower = get_weak_tower(arr, tower_last_attack)
        # 가장 약한 포탑 강화
        arr[weak_tower[0]][weak_tower[1]] += n + m
        tower_last_attack[weak_tower] = t + 1

        # 가장 강한 포탑 선정
        target_tower = get_target_tower(arr, tower_last_attack, weak_tower)
        if len(target_tower) == 0:
            arr[weak_tower[0]][weak_tower[1]] -= n + m
            break

        razer_path = get_razer_path(arr, weak_tower, target_tower)

        weak_tower_power = arr[weak_tower[0]][weak_tower[1]]

        # 레이저 공격
        if razer_path:
            for (y, x) in razer_path[:-1]:
                arr[y][x] -= weak_tower_power // 2

        # 포탄 공격
        else:
            bomb_attack = get_bomb_path(arr, target_tower)
            for (y, x) in bomb_attack:
                if (y, x) != weak_tower:
                    arr[y][x] -= weak_tower_power // 2

            razer_path = bomb_attack

        arr[target_tower[0]][target_tower[1]] -= weak_tower_power

        razer_path.append(weak_tower)
        razer_path.append(target_tower)

        # check
        check = 0
        for i in range(n):
            for j in range(m):
                if arr[i][j] > 0:
                    check = 1
        if check == 0:
            break

        # 포탑 부서짐 & 정비
        for i in range(n):
            for j in range(m):
                # 포탑 부서짐
                if arr[i][j] <= 0:
                    arr[i][j] = 0
                # 포탑 정비
                elif (i, j) not in razer_path:
                    arr[i][j] += 1

    answer = 0
    for i in range(n):
        for j in range(m):
            if arr[i][j] > answer:
                answer = arr[i][j]

    print(answer)


if __name__ == '__main__':
    main()