[코드트리/Python] 포탑 부수기 (삼성 SW 역량테스트)

포탑 부수기

🔍 알고리즘 분류

• 구현
• bfs

💡 문제 풀이

1. 공격자 선정
   • 배열 내 최솟값
   • 공격자가 될 수 있는 포탑들 후보 리스트candidate에 추가
   • candidate를 행과 열의 합, 열 순으로 오름차순 정렬
   • 공격 기록 뒤에서부터 돌며 만약 candidate 내에 있으면 공격자로 지정
   • 없으면 공격자는 candidate[0]
   • 패널티 적용
2. 공격 대상자 선정
   • 위와 동일
   • 조건 수정: 행과 열의 합, 열 순으로 내림차순, 공격 기록 앞에서부터
   • 조건 추가: 공격자가 아님
3. 최단 경로 찾기
   • 무조건 bfs로!! (dfs로 하면 시간초과)
   • 범위 벗어나면 반대쪽으로 넘어가게 모듈러 적용
4. 레이저 공격
   • 공격 관련 리스트에 추가
   • 경로에 있는 포탑들은 공격자 공격력의 반만큼, 공격 대상자는 공격력만큼 피해
   • 공격 받고 음수가 되면 0으로 치환
5. 포탑 공격
   • 공격 관련 리스트에 추가
   • 공격 대상자는 공격력만큼 피해
   • 주위 8칸에 있는 포탑들은 공격자 공격력의 반만큼 피해
     - 8칸 찾을 때에도 모듈러 적용
     • 공격자가 아닌지 확인 필수
   • 공격 받고 음수가 되면 0으로 치환
6. 포탑 정비 및 공격 기록에 공격자 추가
   • 공격 관련 리스트에 없는 포탑들 공격력+1
   • 공격 기록에 공격자 추가
7. 위 과정 k만큼 반복 후, 배열 내 최댓값 출력

📄 코드

• Python

from collections import deque

n, m, k = map(int, input().split())
arr = [list(map(int, input().split())) for _ in range(n)]
attacker_history = [] # 공격 기록 저장

# 공격자 찾기
def find_attacker():
    min_bomb = 5000
    tmp = []
    row, col = 0, 0
    for j in range(m):
        for i in range(n):
            if arr[i][j] != 0 and arr[i][j] <= min_bomb:
                min_bomb = arr[i][j]
                row, col = i, j
                tmp.append((i, j))
    candidate = [bomb for bomb in tmp if arr[bomb[0]][bomb[1]] == min_bomb]
    candidate.sort(key=lambda x : (-(x[0]+x[1]), -x[1]))
    row, col = candidate[0]
    if len(candidate) > 1:
        # 공격한지 가장 최근 포탑 선정
        for i in range(len(attacker_history) - 1, -1, -1):
            for j in range(len(candidate)):
                if attacker_history[i] == candidate[j]:
                    row, col = candidate[j]
                    break
            else:
                continue
            break
    arr[row][col] += n + m
    return row, col

# 공격 대상자 찾기
def find_victim(ax, ay):
    max_bomb = 0
    tmp = []
    row, col = 0, 0
    for j in range(m - 1, -1, -1):
        for i in range(n - 1, -1, -1):
            if arr[i][j] != 0 and not (ax == i and ay == j) and arr[i][j] >= max_bomb:
                max_bomb = arr[i][j]
                row, col = i, j
                tmp.append((i, j))
    candidate = [bomb for bomb in tmp if arr[bomb[0]][bomb[1]] == max_bomb]
    candidate.sort(key=lambda x : (x[0]+x[1], x[1]))
    
    if len(candidate) > 1:
        row, col = candidate[0]
        # 일부만 공격기록 가지고 있을 때
        for candi in candidate:
            if candi not in attacker_history:
                return candi

        # 공격한지 가장 오래된 포탑 선정: 모두 공격 기록을 가지고 있을 때
        for i in range(len(attacker_history)):
            for j in range(len(candidate)):
                if attacker_history[i] == candidate[j]:
                    row, col = candidate[j]
                    break
            else:
                continue
            break

    return row, col

# 우하좌상
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]

# 최단 경로 찾기: dfs 금지(시간초과)
def find_route_bfs(x, y, ex, ey):
    visited = [[False] * m for _ in range(n)]
    queue = deque()
    queue.append((x, y, [(x, y)]))
    visited[x][y] = True

    while queue:
        cx, cy, path = queue.popleft()
        if cx == ex and cy == ey:
            return path
        for i in range(4):
            # 범위 벗어나면 반대쪽으로 가도록 모듈러 적용
            nx = (cx + dx[i]) % n
            ny = (cy + dy[i]) % m
            if not visited[nx][ny] and arr[nx][ny] > 0:
                visited[nx][ny] = True
                queue.append((nx, ny, path + [(nx, ny)]))

    return []

for turn in range(k):
    # 남은 포탑이 1개면 중단
    if sum([(row.count(0)) for row in arr]) == n * m - 1:
        break

    # 공격자, 공격대상자 지정
    ax, ay = find_attacker()
    vx, vy = find_victim(ax, ay)

    # 공격 기록 추가
    if (ax, ay) in attacker_history:
        attacker_history.remove((ax, ay))
    attacker_history.append((ax, ay)) 

    min_route = find_route_bfs(ax, ay, vx, vy)
    attacked = [(ax, ay)] # 공격과 관련 있는 포탑들

    # 레이저 공격
    if len(min_route) > 1:
        # 공격자인 첫 번째 원소 제거
        route = min_route[1:]
        for x, y in route:
            attacked.append((x, y))
            if x == vx and y == vy: # 공격 대상자 일때
                arr[x][y] -= arr[ax][ay]
                if arr[x][y] < 0:
                    arr[x][y] = 0
            else:
                arr[x][y] -= arr[ax][ay] // 2 # 그외: 절반 만큼 피해
                if arr[x][y] < 0:
                    arr[x][y] = 0

    else: # 포탑 공격
        arr[vx][vy] -= arr[ax][ay]
        if arr[vx][vy] < 0:
            arr[vx][vy] = 0
        attacked.append((vx, vy))
        # 시계 방향
        ddx = [-1, -1, 0, 1, 1, 1, 0, -1]
        ddy = [0, 1, 1, 1, 0, -1, -1, -1]
        for i in range(8):
            nx = (vx + ddx[i]) % n
            ny = (vy + ddy[i]) % m
            if arr[nx][ny] != 0 and not (nx == ax and ny == ay): # 공격자가 아니고, 포탑이 있을때
                arr[nx][ny] -= arr[ax][ay] // 2
                if arr[nx][ny] < 0:
                    arr[nx][ny] = 0
                attacked.append((nx, ny))

    # 포탑 정비
    for i in range(n):
        for j in range(m):
            if arr[i][j] != 0 and (i, j) not in attacked:
                arr[i][j] += 1

# 정답 출력: 배열 내 최댓값
print(max([max(row) for row in arr]))

시간: 252ms, 메모리: 23MB