[코드트리/Python] 포탄 부수기

 

포탄 부수다 내 멘탈 부숨

 

 

 

1. 포탄부수기 (골1)

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

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

 

문제

 

풀이

 

CODE1 - 실패

from collections import deque


def solution(n, m, k, board):
    HANDICAP = n + m
    attacker_list = []

    def get_attacker(board, attacker_list):
        min_strongest = 1e9
        min_list = []
        # 공격력이 가장 낮은 포탑 찾기, 거꾸로 탐색해서 열이 큰 순서로 저장되게 하기
        for i in range(n-1, -1, -1):
            for j in range(m-1, -1, -1):
                if 0 < board[i][j] < min_strongest:
                    min_strongest = board[i][j]  # 최솟값 업데이트
                    min_list = [(i, j)]  # 낮은 포탑 리스트 재정의
                elif board[i][j] == min_strongest:
                    min_list.append((i, j))
        # 공격력이 제일 낮은 포탑이 1개면 해당 좌표 반환
        if len(min_list) == 1:
            return min_list[0]
        # 만약 공격력이 낮은 포탑이 2개 이상인 경우
        else:
            # 가장 최근에 공격한 포탑을 반환
            for each in attacker_list[::-1]:
                if each in min_list:
                    return each
            # 행과 열의 합이 가장 큰 포탑 반환
            biggest = 0
            ans = (-1, -1)
            for i in range(len(min_list)):
                if min_list[i][0] + min_list[i][1] > biggest:
                    biggest = min_list[i][0] + min_list[i][1]
                    ans = min_list[i]
            return ans

    def get_victim(board, attacker_list):
        max_strongest = 0
        max_list = []
        # 공격력이 가장 높은 포탑 찾기, 정방향으로 탐색해서 열이 작은 순서로 저장되게 하기
        for i in range(n):
            for j in range(m):
                if i != attacker_list[-1][0] or j != attacker_list[-1][1]:  # 공격자 제외
                    if max_strongest < board[i][j]:
                        max_strongest = board[i][j]  # 최댓값 업데이트
                        max_list = [(i, j)]  # 높은 포탑 리스트 재정의
                    elif board[i][j] == max_strongest:
                        max_list.append((i, j))
        # 공격력이 제일 높은 포탑이 1개면 해당 좌표 반환
        if len(max_list) == 1:
            return max_list[0]
        # 만약 공격력이 높은 포탑이 2개 이상인 경우
        else:
            # 가장 나중에 공격한 포탑을 반환 -> 가장 최근에 공격한 순서부터 존재하면 attacker_list에서 삭제
            for each in attacker_list[::-1]:
                if each in max_list:
                    # 공격 리스트에 하나만 있으면 어쩔 수 없이 리턴
                    if len(max_list) == 1:
                        return each
                    else:
                        # 아닌 경우 후보에서 해당 포탑 제외
                        max_list.remove(each)
            # 행과 열의 합이 가장 작은 포탑 반환
            smallest = 1e9
            ans = (-1, -1)
            for i in range(len(max_list)):
                if max_list[i][0] + max_list[i][1] < smallest:
                    smallest = max_list[i][0] + max_list[i][1]
                    ans = max_list[i]
            return ans

    def bfs_laser(sx, sy, ex, ey):
        visit_check = [[0 for _ in range(m)] for _ in range(n)]
        queue = deque([])
        queue.append((sx, sy, []))
        visit_check[sx][sy] = 1
        dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]  # 우하좌상 반영

        while queue:
            x, y, route = queue.popleft()
            for i in range(4):
                nx, ny = (x + dx[i]) % n, (y + dy[i]) % m

                if 0 <= nx < n and 0 <= ny < m:
                    if not visit_check[nx][ny] and board[nx][ny]:
                        visit_check[nx][ny] = 1
                        if nx == ex and ny == ey:
                            return True, route
                        else:
                            queue.append((nx, ny, route + [(nx, ny)]))

        return False, []

    # k번의 반복
    for _ in range(k):
        is_relation = [[0 for _ in range(m)] for _ in range(n)]
        # 1. 공격자 선정
        attacker_x, attacker_y = get_attacker(board, attacker_list)
        # 1-1. 공격자 리스트 추가
        attacker_list.append((attacker_x, attacker_y))
        # 1-2. 핸디캡 적용
        board[attacker_x][attacker_y] += HANDICAP
        attack_amount = board[attacker_x][attacker_y]
        # 2. 공격자의 공격
        # 2-1. 자신을 제외한 가장 강한 포탑 찾기
        victim_x, victim_y = get_victim(board, attacker_list)
        is_relation[attacker_x][attacker_y] = 1
        is_relation[victim_x][victim_y] = 1
        # 3. 레이저 공격 or 포탄 공격
        # 3-1. 레이저 공격 가능 여부 확인
        can_laser_attack, route = bfs_laser(attacker_x, attacker_y, victim_x, victim_y)
        # 3-2. 레이저 공격 가능
        if can_laser_attack:
            # 공격 경로에 있는 포탑 공격력 감소
            if route:
                for each in route:
                    board[each[0]][each[1]] -= (attack_amount // 2)
                    is_relation[each[0]][each[1]] = 1
            # 공격 대상 포탑 공격력 감소
            board[victim_x][victim_y] -= attack_amount
        # 3-3. 레이저 공격 불가. 포탄 공격 수행
        else:
            board[victim_x][victim_y] -= attack_amount
            dx, dy = [-1, -1, -1, 0, 0, 1, 1, 1], [-1, 0, 1, -1, 1, -1, 0, 1]
            for i in range(8):
                nx = (victim_x + dx[i]) % n
                ny = (victim_y + dy[i]) % m

                if board[nx][ny]:
                    if not (nx == attacker_x and ny == attacker_y):
                        if not (nx == victim_x and ny == victim_y):
                            board[nx][ny] -= (attack_amount // 2)
                            is_relation[nx][ny] = 1

        # 4. 공격 후 공격력 0 이하의 포탑은 부서짐 처리 & 5. 포탑 정비 & 6. 부서지지 않은 포탑이 1개면 종료
        not_broken = 0
        for i in range(n):
            for j in range(m):
                if board[i][j] > 0:
                    not_broken += 1  # 6
                else:
                    board[i][j] = 0  # 4

        if not_broken == 1:
            break
        
        for i in range(n):
            for j in range(m):
                if board[i][j] > 0:
                    if not is_relation[i][j]:
                        board[i][j] += 1  # 5

    # 7. 가장 강한 포탑의 공격력 출력
    biggest = 0
    for i in range(n):
        for j in range(m):
            if board[i][j] > biggest:
                biggest = board[i][j]

    print(biggest)


if __name__ == "__main__":
    n, m, k = map(int, input().split())
    board = []
    for _ in range(n):
        board.append(list(map(int, input().split())))
    solution(n, m, k, board)

 

CODE2 - 성공

from collections import deque


def solution(n, m, k, board):
    HANDICAP = n + m
    attacker_dict = {}
    for i in range(n):
        for j in range(m):
            attacker_dict[(i, j)] = 0


    def get_attacker(board, attacker_dict):
        min_strongest = 1e9
        min_list = []
        max_attack = 0
        # 공격력이 가장 낮은 포탑 찾기
        for i in range(n):
            for j in range(m):
                if 0 < board[i][j] < min_strongest:
                    min_strongest = board[i][j]  # 최솟값 업데이트
                    min_list = [(i, j)]  # 낮은 포탑 리스트 재정의
                    max_attack = attacker_dict[(i, j)]
                elif board[i][j] == min_strongest:
                    # 최근 공격 시점이 더 최근이면 갱신
                    if attacker_dict[(i, j)] > max_attack:
                        max_attack = attacker_dict[(i, j)]
                        min_list = [(i, j)]
                    # 같으면 append, 작으면 신경 안쓰기
                    elif attacker_dict[(i, j)] == max_attack:
                        min_list.append((i, j))
        # 공격력이 제일 낮은 포탑이 1개면 해당 좌표 반환
        if len(min_list) == 1:
            return min_list[0]
            # 만약 공격력이 낮고 최근 공격 시점이 같은 포탑이 2개 이상인 경우
            # 행과 열의 합이 가장 큰 포탑 반환 -> 아닐 경우 열이 큰 포탑 자동 찾기
        else:
            min_list.sort(key=lambda x: (-(x[0] + x[1]), -x[1]))
            return min_list[0]

    def get_victim(board, attacker_dict):
        max_strongest = 0
        max_list = []
        min_attack = 1e9
        # 공격력이 가장 높은 포탑 찾기, 정방향으로 탐색해서 열이 작은 순서로 저장되게 하기
        for i in range(n):
            for j in range(m):
                if not (i == attacker_x and j == attacker_y):  # 공격자 제외
                    if max_strongest < board[i][j]:
                        max_strongest = board[i][j]  # 최댓값 업데이트
                        max_list = [(i, j)]  # 높은 포탑 리스트 재정의
                        min_attack = attacker_dict[(i, j)]
                    elif board[i][j] == max_strongest:
                        if attacker_dict[(i, j)] < min_attack:
                            min_attack = attacker_dict[(i, j)]
                            max_list = [(i, j)]
                        elif attacker_dict[(i, j)] == min_attack:
                            max_list.append((i, j))
        # 공격력이 제일 높은 포탑이 1개면 해당 좌표 반환
        if len(max_list) == 1:
            return max_list[0]
        # 만약 공격력이 높고 공격 시점이 같은 포탑이 2개 이상인 경우
        else:
            # 행과 열의 합이 가장 작은 포탑 반환
            max_list.sort(key=lambda x: (x[0] + x[1], x[1]))
            return max_list[0]

    def bfs_laser(sx, sy, ex, ey):
        visit_check = [[0 for _ in range(m)] for _ in range(n)]
        queue = deque([])
        queue.append((sx, sy, []))
        visit_check[sx][sy] = 1
        dx, dy = [0, 1, 0, -1], [1, 0, -1, 0]  # 우하좌상 반영

        while queue:
            x, y, route = queue.popleft()
            for i in range(4):
                nx, ny = (x + dx[i]) % n, (y + dy[i]) % m

                if 0 <= nx < n and 0 <= ny < m:
                    if not visit_check[nx][ny] and board[nx][ny]:
                        visit_check[nx][ny] = 1
                        if nx == ex and ny == ey:
                            return True, route
                        else:
                            queue.append((nx, ny, route + [(nx, ny)]))

        return False, []

    # k번의 반복
    for t in range(1, k + 1):
        is_relation = [[0 for _ in range(m)] for _ in range(n)]
        # 1. 공격자 선정
        attacker_x, attacker_y = get_attacker(board, attacker_dict)
        # 1-1. 공격자 리스트 추가
        attacker_dict[(attacker_x, attacker_y)] = t
        # 1-2. 핸디캡 적용
        board[attacker_x][attacker_y] += HANDICAP
        attack_amount = board[attacker_x][attacker_y]
        # 2. 공격자의 공격
        # 2-1. 자신을 제외한 가장 강한 포탑 찾기
        victim_x, victim_y = get_victim(board, attacker_dict)
        is_relation[attacker_x][attacker_y] = 1
        is_relation[victim_x][victim_y] = 1
        # 3. 레이저 공격 or 포탄 공격
        # 3-1. 레이저 공격 가능 여부 확인
        can_laser_attack, route = bfs_laser(attacker_x, attacker_y, victim_x, victim_y)
        # 3-2. 레이저 공격 가능
        if can_laser_attack:
            # 공격 경로에 있는 포탑 공격력 감소
            if route:
                for each in route:
                    board[each[0]][each[1]] -= (attack_amount // 2)
                    is_relation[each[0]][each[1]] = 1
            # 공격 대상 포탑 공격력 감소
            board[victim_x][victim_y] -= attack_amount
        # 3-3. 레이저 공격 불가. 포탄 공격 수행
        else:
            board[victim_x][victim_y] -= attack_amount
            dx, dy = [-1, -1, -1, 0, 0, 1, 1, 1], [-1, 0, 1, -1, 1, -1, 0, 1]
            for i in range(8):
                nx = (victim_x + dx[i]) % n
                ny = (victim_y + dy[i]) % m

                if board[nx][ny]:
                    if not (nx == attacker_x and ny == attacker_y):
                        if not (nx == victim_x and ny == victim_y):
                            board[nx][ny] -= (attack_amount // 2)
                            is_relation[nx][ny] = 1

        # 4. 공격 후 공격력 0 이하의 포탑은 부서짐 처리 & 5. 포탑 정비 & 6. 부서지지 않은 포탑이 1개면 종료
        not_broken = 0
        for i in range(n):
            for j in range(m):
                if board[i][j] > 0:
                    not_broken += 1  # 6
                else:
                    board[i][j] = 0  # 4

        if not_broken == 1:
            break

        for i in range(n):
            for j in range(m):
                if board[i][j] > 0:
                    if not is_relation[i][j]:
                        board[i][j] += 1  # 5

    # 7. 가장 강한 포탑의 공격력 출력
    biggest = 0
    for i in range(n):
        for j in range(m):
            if board[i][j] > biggest:
                biggest = board[i][j]

    print(biggest)


if __name__ == "__main__":
    n, m, k = map(int, input().split())
    board = []
    for _ in range(n):
        board.append(list(map(int, input().split())))
    solution(n, m, k, board)

• 구현 & bfs
• 정말 겨우겨우겨우겨우 풀었다. 너무 힘들고 진이 빠졌지만, 그 과정에서 정말 많이 배웠다. 실전이 아닌 미리 이런 경험을 해볼 수 있는 것에 감사하다. 
• 문제를 풀면서 배운 점
  1. 허투로 주는 조건은 없다. 해당 조건이 왜 주어졌을지, 어떤 식으로 문제를 풀기 바라는 것 같은지 출제자의 의도를 깊게 고민해보자.
  2. 조건들이 로직 속에서 잘 구현되고 있는지 꼼꼼하게 고민되자. 예를 들어 1 ~ 4 순위를 통해 답을 골라가는 과정에서 if 문으로 갈래가 나뉜다면 갈래가 나뉜 후에도 차 순위의 조건들이 모든 곳에서 잘 검증되고 있는지 파악하자.
  3. 반례를 생각하는 과정에서는 무조건 print를 찍거나, 확인하기보다는 문제에서 주어진 조건들과 내 코드를 비교해서 문제가 있을 법한 상황을 생각하고 그 후 그에 맞는 반례를 고민해서 문제를 해결해보자
• 제출기록