[삼성 SW 역량 테스트 기출, Python] 포탑 부수기 풀이

2023 상반기 오전 1번 문제로 나왔던 '포탑 부수기' 문제의 python 풀이입니다. 

1. 문제 링크

https://www.codetree.ai/ko/frequent-problems/problems/destroy-the-turret/description

삼성 코딩테스트 기출 문제 설명: 포탑 부수기 | 코드트리

 

2. 한줄평

문제 자체는 어렵지 않았습니다. simulation + bfs로 최단 경로 찾는 문제입니다. 찾는거에서 영역 밖을 통해 이동할 수 있는게 좀 새롭긴 했지만 구현자체는 쉬웠습니다. 다만 역시나 그렇듯 조건이 너무 많아서 놓치기가 쉬워요ㅠ

저같은 경우 열 우선인데 행 우선으로 했다가 시간 엄청 잡아먹었네요..왜 잘못읽었을까요 실전엔 안그래야할텐데🥲

역시나 교훈은 꼼꼼히 읽자.... 다 풀고 나면 문제 한줄한줄 읽으면서 다르게 파악한거 있는지 체크하자!!

 

3. 코드

N, M, K = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(N)]
last_attack_graph = [[0]*M for _ in range(N)]

current_attack_graph = [[False] * M for _ in range(N)]


def get_attacker():
    attacker_pos = None
    attacker_power = None
    attacker_time = None
    for i in range(N):
        for j in range(M):
            temp_power = graph[i][j]
            if temp_power == 0:
                continue
            temp_time = last_attack_graph[i][j]
            is_change = False
            if attacker_power == None or temp_power < attacker_power: # 1번 우선순위
                is_change = True
            elif temp_power == attacker_power:
                if temp_time > attacker_time: # 2번 우선순위
                    is_change = True
                elif temp_time == attacker_time:
                    attacker_sum = attacker_pos[0]+attacker_pos[1]
                    temp_sum = i+j
                    if temp_sum > attacker_sum:
                        is_change = True
                    elif temp_sum == attacker_sum:
                        if j > attacker_pos[1]:
                            is_change = True

            if is_change == True:
                attacker_pos = (i, j)
                attacker_power = graph[i][j]
                attacker_time = last_attack_graph[i][j]

    return attacker_pos

def get_attack_spot(attacker_pos):
    att_spot_pos = None
    att_spot_power = None
    att_spot_time = None
    for i in range(N):
        for j in range(M):
            temp_power = graph[i][j]
            if temp_power == 0:
                continue
            if (i, j) == attacker_pos:
                continue

            temp_time = last_attack_graph[i][j]
            is_change = False
            if att_spot_power == None or temp_power > att_spot_power:  # 1번 우선순위
                is_change = True
            elif temp_power == att_spot_power:
                if temp_time < att_spot_time:  # 2번 우선순위
                    is_change = True
                elif temp_time == att_spot_time:
                    att_spot_sum = att_spot_pos[0] + att_spot_pos[1]
                    temp_sum = i + j
                    if temp_sum < att_spot_sum:
                        is_change = True
                    elif temp_sum == att_spot_sum:
                        if j < att_spot_pos[1]:
                            is_change = True

            if is_change == True:
                att_spot_pos = (i, j)
                att_spot_power = graph[i][j]
                att_spot_time = last_attack_graph[i][j]

    return att_spot_pos

from collections import deque
def get_minimum_path(attacker_pos, attack_spot_pos):
    dx = [0, 1, 0, -1]
    dy = [1, 0, -1, 0]
    start_x, start_y = attacker_pos
    end_x, end_y = attack_spot_pos

    queue = deque()
    queue.append([(start_x, start_y)])

    visited_map = [[False] * M for _ in range(N)]
    visited_map[start_x][start_y] = True

    while(queue):
        path = queue.popleft()
        cur_x, cur_y = path[-1]
        if (cur_x,cur_y) == (end_x, end_y):
            return path

        for dir in range(4):
            new_x, new_y = (cur_x+dx[dir])%N, (cur_y + dy[dir])%M
            if graph[new_x][new_y] <= 0:
                continue
            elif visited_map[new_x][new_y] == False:
                queue.append(path[:]+[(new_x, new_y)])
                visited_map[new_x][new_y] = True

    return []

def do_step1_attack(attacker_pos, attack_spot_pos): # 했으면 True, 안했으면 False return
    global current_attack_graph
    path = get_minimum_path(attacker_pos, attack_spot_pos)
    power = graph[attacker_pos[0]][attacker_pos[1]]

    if len(path) == 0:
        return False

    for i in range(1, len(path)-1):
        pos_x, pos_y = path[i]
        graph[pos_x][pos_y] = max(graph[pos_x][pos_y] - power//2, 0)
        current_attack_graph[pos_x][pos_y] = True

    graph[attack_spot_pos[0]][attack_spot_pos[1]] = max(graph[attack_spot_pos[0]][attack_spot_pos[1]] - power, 0)
    current_attack_graph[attack_spot_pos[0]][attack_spot_pos[1]] = True
    current_attack_graph[attacker_pos[0]][attacker_pos[1]] = True

    return True

def do_step2_attack(attacker_pos, attack_spot_pos):
    global current_attack_graph, graph

    attack_spot_x, attack_spot_y = attack_spot_pos
    current_attack_graph[attacker_pos[0]][attacker_pos[1]] = True
    power = graph[attacker_pos[0]][attacker_pos[1]]


    for i in range(attack_spot_x-1, attack_spot_x+2):
        real_spot_x = i % N
        for j in range(attack_spot_y-1, attack_spot_y+2):
            real_spot_y = j % M
            if graph[real_spot_x][real_spot_y] <= 0:
                pass
            elif (real_spot_x, real_spot_y) == attacker_pos:
                pass
            elif (real_spot_x, real_spot_y) == attack_spot_pos:
                current_attack_graph[real_spot_x][real_spot_y] = True
                graph[real_spot_x][real_spot_y] = max(graph[real_spot_x][real_spot_y]-power, 0)
            else:
                current_attack_graph[real_spot_x][real_spot_y] = True
                graph[real_spot_x][real_spot_y] = max(graph[real_spot_x][real_spot_y] - power//2, 0)

# 전체 for 문에서 가장 최신 공격 리스트는 update해야함
def simulation(time):
    global last_attack_graph, current_attack_graph
    current_attack_graph = [[False] * M for _ in range(N)]
    attacker_pos = get_attacker()
    attack_spot_pos = get_attack_spot(attacker_pos)
    if attack_spot_pos == None:
        return False

    last_attack_graph[attacker_pos[0]][attacker_pos[1]] = time
    graph[attacker_pos[0]][attacker_pos[1]] += (N+M)



    is_do = do_step1_attack(attacker_pos, attack_spot_pos)
    if is_do == False:
        do_step2_attack(attacker_pos, attack_spot_pos)

    for i in range(N):
        for j in range(M):
            if graph[i][j] > 0 and current_attack_graph[i][j] == False:
                graph[i][j] += 1

    return True

for i in range(K):
    if simulation(i+1) == False:
        break


row_max = []
for i in range(N):
    row_max.append(max(graph[i]))


print(max(row_max))

공격대상이 없는 경우(포탑이 하나만 남았을 경우) get_attack_spot 함수가 None을 return 하도록 하여 False를 return 하도록 하였습니다. 

부서지지 않은 포탑의 개수가 1개가 되면 즉시 종료해야한다고 해서, 공격할때까지는 포탑의 개수가 2개 이상이였다가 공격하고 난 뒤 남은 포탑의 개수가 1개인 경우를 체크해야하나 고민했지만 -> 그럴 경우 포탑 정비의 대상인 포탑이 하나도 남아있지 않기 때문에 one_simulation() 루프를 끝까지 돌더라도 상태가 달라지지 않습니다. 그래서 굳이 체크하지 않았답니다.