[코드트리] 포탑 부수기 python 문제풀이 (2023 삼성전자 오전 1번문제)

2023 삼성 코테를 보고와서 복기겸 다시 한번 풀어보았다.

문제는 코드트리에서 확인 가능하다.

 

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

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

 

 

해당 문제에서 주의해서 풀어야 하는점은 다음과 같다.

 

1. 공격자 포탑과 타겟 포탑을 선정하는 과정

해결방법 : sort를 이용하여 해결

 

2. 레이저 공격 과정

이부분이 시험장에서 조금 말썽을 부렸다. 원래 시험장에서 풀때는 이동한 경로를 리스트에 전부 저장해서 그 리스트를 이용하여 문제를 해결하였는데, 굉장히 코드도 길어지고 시간도 굉장히 많이 잡아먹었다.

해결 방법 : 리스트에 전부다 저장해서 통째로 가지고 다닐 필요없이, Back Trace를 이용하여 어디서부터 왔는지 그 좌표를 기록해주면서 역추적해나가는 과정을 거치면 손쉽게 해결된다.

 

3. 포탄 공격 과정

포탄은 8방향으로 퍼지면서 공격을 하는데, 만약 타겟인 타워와 붙어있다면, 공격자 포탑도 포탄 공격을 받는다. 실수하기 쉬우니 예외처리를 잘해줘야 한다.

 

4. 코드트리에서 문제를 읽어도 문제 길이가 상당하다. 실제 시험장에서는 훨씬더 길어서 너무 당황했다.

 

 

코드

from collections import deque

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

# 공격 시간을 기록하기 위한 배열 선언
last_attacked = [[0] * m for _ in range(n)]

# 게임 종료 확인을 위한 check함수
def check():
    cnt = 0
    for i in range(n):
        for j in range(m):
            if graph[i][j] != 0:
                cnt += 1
    # 만약 포탑이 하나가 남았다면
    # True를 반환시켜 게임을 종료시킴
    if cnt == 1:
        return True
    else:
        return False 

def attacker() -> tuple:
    min_value = 1e9
    attacker_arr = []
    # 공격력이 가장 낮은 값 찾기
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0:
                continue
            else:
                # 해당 값을 발견하면 min_value 값으로 바꿔주기
                if min_value > graph[i][j]:
                    min_value = graph[i][j]

    #해당 공격력인 칸 좌표 선택해서 attack_arr에 저장하기
    for i in range(n):
        for j in range(m):
            if graph[i][j] == min_value:
                attacker_arr.append((i, j, last_attacked[i][j]))

    # 조건에 맞게 정렬 해줌
    # 정렬 조건 (가장 최근에 공격, 행과 열의 합 큰, 열 값이 가장 큰)
    attacker_arr.sort(key=lambda x : ((x[2], x[0] + x[1], x[1])), reverse= True)

    # attaker_pos의 x, y 좌표를 반환해줌
    return attacker_arr[0][0], attacker_arr[0][1]

def target() -> tuple:
    # attacker와 같은 로직으로 구현
    max_value = -1
    target_arr = []
    for i in range(n):
        for j in range(m):
            if graph[i][j] == 0:
                continue
            else:
                if graph[i][j] > max_value:
                    max_value = graph[i][j]

    for i in range(n):
        for j in range(m):
            if graph[i][j] == max_value:
                target_arr.append((i, j, last_attacked[i][j]))

    # 조건에 맞게 정렬
    # 공격한지 오래된 포탑, 행과 열이 합이 작은, 열 값이 가장 작은 순
    target_arr.sort(key=lambda x : (x[2], (x[0] + x[1]), x[1]))

    return target_arr[0][0], target_arr[0][1]


def attack(x, y, attack_power):
    # 공격한걸 기록해줌
    is_attack[x][y] = True
    # 해당 좌표를 attack_power만큼 공격함
    graph[x][y] -= attack_power

    # 만약 0보다 작으면 0으로 맞춰주기
    if graph[x][y] < 0:
        graph[x][y] = 0

def laser_attack(attacker_pos, traget_pos):
    visited = [[False] * m for _ in range(n)]

    # Back Trace를 위한 배열 선언
    come = [[None] * m for _ in range(n)]
    # 4개 방향으로 탐색한다
    # 우선순위 -> (우, 하, 좌, 상)
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    queue = deque()
    queue.append(attacker_pos)
    visited[attacker_pos[0]][attacker_pos[1]] = True

    while queue:
        x, y = queue.popleft()
        for d in range(4):
            # 격자가 이어짐
            nx = (x + dx[d]) % n
            ny = (y + dy[d]) % m
            if visited[nx][ny] == False and graph[nx][ny] != 0:
                visited[nx][ny] = True
                queue.append((nx, ny))
                # 역추적을 위해 전에 온 좌표를 기록해줌
                come[nx][ny] = (x, y)
                
	# 역추적 확인을 위한 print()
    # for i in come:
    #     print(i)

    
    # 만약 해당 좌표에 도달할수 없다면 공격을 진행하는게 아닌 False를 리턴
    if visited[target_pos[0]][target_pos[1]] == False:
        return False

	#공격이 가능하다면
    attacker_x, attacker_y = attacker_pos
    x, y = target_pos

    # 공격 진행
    while x != attacker_x or y != attacker_y:
        # 공격 루트는 공격력 // 2 만큼
        attack_power = graph[attacker_x][attacker_y] //2

        # 해당 공격 좌표는 공격력 만큼
        if x == target_pos[0] and y == target_pos[1]:
            attack_power = graph[attacker_x][attacker_y]

        # 공격하기
        attack(x, y, attack_power)

        # 역추적하기
        x, y = come[x][y]
	
    #공격을 진행했으니 True를 반환
    return True



def potan_attack(attack_pos, target_pos):

    # 대각선을 포함한 8개의 값
    dx = [-1, -1, -1, 0, 0, 1, 1, 1]
    dy = [-1, 0, 1, -1, 1, -1, 0, 1]

    # 타겟을 바로 공격함
    x, y = target_pos
    # 공격력은 그대로 적용
    attack_power = graph[attack_pos[0]][attack_pos[1]]
    attack(x, y, attack_power)

    # 타겟 주위 8방향을 공격함.
    for d in range(8):
        # 격자가 이어져있음
        nx = (x + dx[d]) % n
        ny = (y + dy[d]) % m
        # 좌표가 공격자이면 무시해야됨
        if nx == attack_pos[0] and ny == attack_pos[1]:
            continue
        # 공격력의 반만큼 공격함
        attack_power = graph[attack_pos[0]][attack_pos[1]] // 2
        attack(nx, ny, attack_power)

# 포탑 정비하기
def repair():
    for i in range(n):
        for j in range(m):
        	#공격을 받지 않았고, 해당 좌표가 포탑이라면 정비
            if is_attack[i][j] == False and graph[i][j] != 0:
                graph[i][j] += 1


# simulate 시작
for time in range(1, k + 1):
    # 만약 종료 조건을 만족한다면 바로 종료
    if check():
        break

    # 공격자 좌표 얻어옴
    attack_pos = attacker()

    # 타겟 좌표를 얻어옴
    target_pos = target()

    # 핸디캡을 부여함
    graph[attack_pos[0]][attack_pos[1]] += n + m

    # 공격시간을 갱신
    last_attacked[attack_pos[0]][attack_pos[1]] = time

    # 공격을 체크하는 배열 선언
    is_attack = [[False] * m for _ in range(n)]
    is_attack[attack_pos[0]][attack_pos[1]] = True

    # 레이저 공격 시작
    if laser_attack(attack_pos, target_pos):
        pass
    #레이저 공격이 안된다면 포탄던지기
    else:
        potan_attack(attack_pos, target_pos)

    # 정비하기
    repair()

# 가장 강한 포탑의 공격력을 출력함
answer = 0
for i in range(n):
    for j in range(m):
        answer = max(answer, graph[i][j])

print(answer)

 

 

해당 문제에서는 시간복잡도가 O(K * N * M * log(NM)) 이렇게 나오지만 실제 시험문제에서는 testcase를 input으로 한번 더 받아서 O(T * K * N * M * log(NM))가 될것이다.