코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
문제
격자가 있고, 모든 위치에는 포탑이 존재합니다. (즉, 포탑의 개수는 개)
각 포탑에는 공격력이 존재하며, 상황에 따라 공격력이 줄어들거나 늘어날 수 있습니다. 또한, 공격력이 이하가 된다면, 해당 포탑은 부서지며 더 이상의 공격을 할 수 없습니다. 최초에 공격력이 인 포탑 즉, 부서진 포탑이 존재할 수 있습니다.
아래와 같은 크기의 격자를 생각해보겠습니다. , , 를 포함한 총 개의 칸은 이미 부서진 포탑을 의미합니다.
하나의 턴은 다음의 4가지 액션을 순서대로 수행하며, 총 번 반복됩니다.
만약 부서지지 않은 포탑이 개가 된다면 그 즉시 중지됩니다.
1. 공격자 선정
부서지지 않은 포탑 중 가장 약한 포탑이 공격자로 선정됩니다. 공격자로 선정되면 가장 약한 포탑이므로, 핸디캡이 적용되어 만큼의 공격력이 증가됩니다.
가장 약한 포탑은 다음의 기준으로 선정됩니다.
- 공격력이 가장 낮은 포탑이 가장 약한 포탑입니다.
- 만약 공격력이 가장 낮은 포탑이 2개 이상이라면, 가장 최근에 공격한 포탑이 가장 약한 포탑입니다. (모든 포탑은 시점 에 모두 공격한 경험이 있다고 가정하겠습니다.)
- 만약 그러한 포탑이 2개 이상이라면, 각 포탑 위치의 행과 열의 합이 가장 큰 포탑이 가장 약한 포탑입니다.
- 만약 그러한 포탑이 2개 이상이라면, 각 포탑 위치의 열 값이 가장 큰 포탑이 가장 약한 포탑입니다.
위의 예시에서 공격자를 선정해보면, 가장 낮은 공격력은 이기 때문에, 아래 그림과 같이 위치에 있는 포탑이 공격자로 선정되며, 공격력이 만큼 증가하여 가 됩니다.
2. 공격자의 공격
위에서 선정된 공격자는 자신을 제외한 가장 강한 포탑을 공격합니다.
가장 강한 포탑은 위에서 정한 가장 약한 포탑 선정 기준의 반대이며, 다음과 같습니다.
- 공격력이 가장 높은 포탑이 가장 강한 포탑입니다.
- 만약 공격력이 가장 높은 포탑이 2개 이상이라면, 공격한지 가장 오래된 포탑이 가장 강한 포탑입니다. (모든 포탑은 시점 에 모두 공격한 경험이 있다고 가정하겠습니다.)
- 만약 그러한 포탑이 2개 이상이라면, 각 포탑 위치의 행과 열의 합이 가장 작은 포탑이 가장 강한 포탑입니다.
- 만약 그러한 포탑이 2개 이상이라면, 각 포탑 위치의 열 값이 가장 작은 포탑이 가장 강한 포탑입니다.
위의 예시에서 공격 대상자를 선정해보겠습니다. 공격 대상인 가장 강한 포탑은 공격력이 가장 큰 의 공격력을 가진 위치의 포탑이 됩니다.
공격을 할 때에는 레이저 공격을 먼저 시도하고, 만약 그게 안 된다면 포탄 공격을 합니다. 각 공격의 규칙은 다음과 같습니다.
(1) 레이저 공격
레이저는 다음의 규칙으로 움직입니다.
- 상하좌우의 4개의 방향으로 움직일 수 있습니다.
- 부서진 포탑이 있는 위치는 지날 수 없습니다.
- 가장자리에서 막힌 방향으로 진행하고자 한다면, 반대편으로 나옵니다. (예를 들어, 위의 예시에서 에서 오른쪽으로 두번 이동한다면, -> -> 순으로 이동합니다.)
레이저 공격은 공격자의 위치에서 공격 대상 포탑까지의 최단 경로로 공격합니다. 만약 그러한 경로가 존재하지 않는다면 (2) 포탄 공격을 진행합니다. 만약 경로의 길이가 똑같은 최단 경로가 2개 이상이라면, 우/하/좌/상의 우선순위대로 먼저 움직인 경로가 선택됩니다.
최단 경로가 정해졌으면, 공격 대상에는 공격자의 공격력 만큼의 피해를 입히며, 피해를 입은 포탑은 해당 수치만큼 공격력이 줄어듭니다. 또한 공격 대상을 제외한 레이저 경로에 있는 포탑도 공격을 받게 되는데, 이 포탑은 공격자 공격력의 절반 만큼의 공격을 받습니다. (절반이라 함은 공격력을 로 나눈 몫을 의미합니다.)
(2) 포탄 공격
공격 대상에 포탄을 던집니다. 공격 대상은 공격자 공격력 만큼의 피해를 받습니다. 추가적으로 주위 8개의 방향에 있는 포탑도 피해를 입는데, 공격자 공격력의 절반 만큼의 피해를 받습니다. (절반이라 함은 공격력을 로 나눈 몫을 의미합니다.) 공격자는 해당 공격에 영향을 받지 않습니다. 만약 가장자리에 포탄이 떨어졌다면, 위에서의 레이저 이동처럼 포탄의 추가 피해가 반대편 격자에 미치게 됩니다.
위의 예시에서 공격자가 공격 대상을 레이저로 공격하기 위한 최단 경로는 아래 그림과 같습니다. 최단 경로가 2개 이상 있지만, 오른쪽으로 먼저 움직이는 것이 우선 순위가 높기 때문에, 다음의 경로가 선택된 것입니다. 최단 경로가 정해졌기 때문에, 공격 대상에는 만큼의 피해를 입히고, 경로에 있는 포탑에는 만큼의 피해를 입힙니다.
3. 포탑 부서짐
공격을 받아 공격력이 이하가 된 포탑은 부서집니다.
4. 포탑 정비
공격이 끝났으면, 부서지지 않은 포탑 중 공격과 무관했던 포탑은 공격력이 씩 올라갑니다. 공격과 무관하다는 뜻은 공격자도 아니고, 공격에 피해를 입은 포탑도 아니라는 뜻입니다.
위의 예시에서 공격과 무관했던 다음 4개의 포탑은 정비를 받아 공격력이 씩 증가합니다. 이렇게 첫 번째 턴이 종료됩니다.
다음 두 번째 턴이 시작되면, 다시 공격자 선정이 시작됩니다.
첫 번째 규칙에 따라 가장 공격력이 작은 만큼의 공격력을 가진 , , , 위치의 포탑이 공격자 후보가 됩니다. 두 번째 규칙에 의해 가장 최근에 공격한 포탑인 포탑이 가장 약한 포탑이므로 공격자로 선정됩니다. 마찬가지로 핸디캡으로 만큼의 공격력을 얻습니다.
다음으로 공격 대상을 선택하면, 공격력이 가장 높은 가 선택됩니다. 공격자의 위치에서 공격 대상의 위치까지 이동하는 경로가 없기 때문에, 레이저 공격은 불가능하여 포탄 공격을 수행하게 됩니다. 포탄은 공격 대상인 위치에 떨어지며, 공격 대상은 만큼의 피해를 받고, 주변 8개의 방향에 있는 포탑은 만큼의 피해를 받습니다.
마지막으로 공격과 무관했던 포탑은 정비를 받아 만큼의 공격력을 얻지만, 위의 예시에서는 부서지지 않은 포탑 중 공격과 무관했던 포탑이 없으므로, 최종 모습은 다음과 같습니다.
전체 과정이 종료된 후 남아있는 포탑 중 가장 강한 포탑의 공격력을 출력하는 프로그램을 작성해보세요.
입력
첫 번째 줄에 , , 가 공백을 사이에 두고 주어집니다.
두 번째 줄부터 개의 줄에 걸쳐서 격자에 대한 정보가 주어집니다. 단, 최초에 부서지지 않은 포탑은 최소 개 이상 존재합니다.
출력
첫 번째 줄에 번의 턴이 종료된 후 남아있는 포탑 중 가장 강한 포탑의 공격력을 출력합니다.
풀이
정말정말 할게 많고 복잡하다. 하나하나 꼼꼼하게 문제를 확인하고 풀어야할 문제를 정리해야 할 것..
23년 상반기 문제라서 그런지 모르겠는데 23년 하반기에도 비슷한 느낌의 문제가 나온 것 같다. (그저 내 느낌..) 더 어렵고 복잡해진 느낌..
문제는 크게 2가지로 나눈다.
1. 레이저 공격
2. 포탄 공격
해야할 일을 나눈다면 다음과 같다.
- 공격자 선정
- 공격 받을 포탑 선정
- 레이저 공격
- 포탑 공격
- 포탑 부수기
- 포탑 정비
공격자 선정(select_attack)
공격자는 포탑 중 공격력이 가장 약한 포탑으로 선정한다. 가장 약한 포탑을 선정하는 것은 크게 어렵지 않으나 공격자로 선정될 후보가 여럿인 경우 우선순위에 따라 선정을 해야한다. 대부분 우선순위는 리스트 정렬을 이용해 쉽게 해결 할 수 있다. 문제에서 제시한 우선순위는 가장 최근에 공격한 포탑, 행과 열의 합이 가장 큰 포탑, 열값이 가장 큰 포탑 순이다. 가장 최근에 공격한 포탑 조건이 존재하기 때문에 포탑이 공격한 시기를 저장해 놓아야 한다. history 리스트를 이용해 포탑이 공격한 시기를 저장한다. 또한, 나중에 포탑 정비 할때 공격과 무관한 포탑을 조사해야 하기 때문에 공격과 관련이 있는 포탑을 표시 해 놓는다.
공격자로 선택을 받게 되면 공격력이 n+m만큼 증가하게 된다.
def select_attack(game_map):
min_value = 6000
candidate_a = []
for i in range(n):
for j in range(m):
if game_map[i][j] < min_value and game_map[i][j] > 0:
candidate_a = []
min_value = game_map[i][j]
candidate_a.append([history[i][j], i+j ,j, i])
elif game_map[i][j] == min_value:
candidate_a.append([history[i][j], i+j ,j, i])
# 리스트 정렬을 통한 우선순위 조건 충족
candidate_a.sort(reverse=True)
x, y = candidate_a[0][3], candidate_a[0][2]
# 공격력 증가
game_map[x][y] = game_map[x][y] + n + m
return x, y
공격 받을 포탑 선정(select_defense)
공격자가 선정이 되면, 공격을 받을 포탑을 선택해야한다. 공격자를 제외한 공격력이 가장 높은 포탑을 선택한다. 공격자 선정과 같은 알고리즘을 이용하되, 우선순위를 올림차순으로 정렬하면 원하는 값을 얻을 수 있다.
def select_defense(game_map, ax, ay):
max_value = -1
candidate_d = []
for i in range(n):
for j in range(m):
# 공격자 제외
if i == ax and j == ay:
continue
if game_map[i][j] > max_value and game_map[i][j] > 0:
candidate_d = []
max_value = game_map[i][j]
candidate_d.append(([history[i][j], i+j ,j, i]))
elif game_map[i][j] == max_value:
candidate_d.append(([history[i][j], i + j, j, i]))
# 리스트 정렬 오름차순으로 우선순위 충족
candidate_d.sort()
x, y = candidate_d[0][3], candidate_d[0][2]
return x, y
레이저 공격(laser_attack)
공격은 레이저 공격을 먼저 시도하고, 안된다면 포탄 공격을 시도한다.
레이저 공격은 격자 밖을 넘어서지 않고 원통 처럼 연결되어 움직일 수 있다. 이동할 때 %를 이용할 것.
공격자의 위치에서 대상 포탑 까지 최단 경로를 찾아 공격해야 하므로, BFS 알고리즘을 이용해 최단거리를 찾는다.
최단 경로가 2개 이상일 경우, 우/하/좌/상의 우선순위가 있기 때문에 탐색 순서를 우선순위대로 지정한다면 고려하지 않아도 된다. 방향은 4방향만 움직이기 때문에 처음 방향리스트를 설정할 때, [우하좌상 / 대각선 ]순으로 선언한다.
최단 경로를 정한 후, 대상 포탑은 공격력 만큼 피해를 입고, 경로에 속한 포탑은 그 절반 만큼의 피해를 입게 된다. 경로에 속한 포탑을 공격하기 위해 route리스트를 이용해 저장한다.
만약, 대상 포탑에 도달하지 못한다면 포탑 공격을 시도한다.
def laser_attack(ax, ay, dex, dey, point):
q = deque()
q.append([ax, ay, []])
visited = [[0] * m for _ in range(n)]
visited[ax][ay] = True
while q:
x, y, route = q.popleft()
for d in range(4):
nx = (x + dx[d]) % n
ny = (y + dy[d]) % m
# 방문을 한 칸이거나 부서진 포탑인 경우
if visited[nx][ny] : continue
if game_map[nx][ny] == 0: continue
# 타겟에 도달한 경우
if nx == dex and ny == dey:
game_map[nx][ny] -= point
for rx, ry in route:
game_map[rx][ry] -= point//2
# 공격과 관련 있음
attack[rx][ry] = True
return True
temp = route[:]
temp.append([nx, ny])
visited[nx][ny] = True
q.append([nx, ny, temp])
# 타겟에 도달하지 못한 경우
return False
포탑공격(turret_attack)
레이저 공격에 비해 쉽게 구현이 가능하다. 대상 포탑에 공격자 공격력 만큼 피해를 주고, 대상 포탑 주위 8개 방향의 포탑에 그 절반 만큼의 피해를 입힌다.
def turret_attack(ax, ay, dex, dey, point):
game_map[dex][dey] -= point
for d in range(8):
nx = (dex + dx[d]) % n
ny = (dey + dy[d]) % m
# 공격 포탑은 제외
if nx == ax and ny == ay: continue
game_map[nx][ny] -= point // 2
#공격과 관련 있음을 표시
attack[nx][ny] = True
포탑부수기(break_check)
공격 이후, 공격력이 0 이하가 된 포탑을 삭제한다.
def break_check():
for i in range(n):
for j in range(m):
if game_map[i][j] < 0:
game_map[i][j] = 0
포탑정비
포탑을 공격 하면서, 공격과 관련있는 포탑을 표시했다. 포탑 정비에서는 공격과 무관했던 포탑의 공격력을 1씩 올리는 작업을 한다. 포탑을 정비 한 후, 부서지지 않은 포탑이 1개가 된다면 즉시 공격을 중지해야한다.
def max_check():
return max([max(line) for line in game_map])
def maintain_turret():
turret = []
turret_cnt = 0
for i in range(n):
for j in range(m):
# 포탑이 부서진 경우
if game_map[i][j] == 0:
continue
turret_cnt += 1
# 공격과 관련이 있는 경우
if attack[i][j]: continue
turret.append([i,j])
if turret_cnt == 1:
print(max_check())
exit(0)
for i, j in turret:
game_map[i][j] += 1
코드
from collections import deque
from pprint import pprint
n, m, k = map(int, input().split())
game_map = [list(map(int, input().split())) for _ in range(n)]
# 공격한 순서 저장
history = [[0]*m for i in range(n)]
# 우/하/좌/상 /상우/상좌/하우/하좌
dx = [0, 1, 0, -1, -1, -1, 1, 1]
dy = [1, 0, -1, 0, 1, -1, 1, -1]
def select_attack(game_map):
min_value = 6000
candidate_a = []
for i in range(n):
for j in range(m):
if game_map[i][j] < min_value and game_map[i][j] > 0:
candidate_a = []
min_value = game_map[i][j]
candidate_a.append([history[i][j], i+j ,j, i])
elif game_map[i][j] == min_value:
candidate_a.append([history[i][j], i+j ,j, i])
candidate_a.sort(reverse=True)
x, y = candidate_a[0][3], candidate_a[0][2]
game_map[x][y] = game_map[x][y] + n + m
return x, y
def select_defense(game_map, ax, ay):
max_value = -1
candidate_d = []
for i in range(n):
for j in range(m):
if i == ax and j == ay:
continue
if game_map[i][j] > max_value and game_map[i][j] > 0:
candidate_d = []
max_value = game_map[i][j]
candidate_d.append(([history[i][j], i+j ,j, i]))
elif game_map[i][j] == max_value:
candidate_d.append(([history[i][j], i + j, j, i]))
candidate_d.sort()
x, y = candidate_d[0][3], candidate_d[0][2]
return x, y
def laser_attack(ax, ay, dex, dey, point):
q = deque()
q.append([ax, ay, []])
visited = [[0] * m for _ in range(n)]
visited[ax][ay] = True
while q:
x, y, route = q.popleft()
for d in range(4):
nx = (x + dx[d]) % n
ny = (y + dy[d]) % m
# 방문을 한 칸이거나 부서진 포탑인 경우
if visited[nx][ny] : continue
if game_map[nx][ny] == 0: continue
# 타겟에 도달한 경우
if nx == dex and ny == dey:
game_map[nx][ny] -= point
for rx, ry in route:
game_map[rx][ry] -= point//2
# 공격과 관련 있음
attack[rx][ry] = True
return True
temp = route[:]
temp.append([nx, ny])
visited[nx][ny] = True
q.append([nx, ny, temp])
# 타겟에 도달하지 못한 경우
return False
def turret_attack(ax, ay, dex, dey, point):
game_map[dex][dey] -= point
for d in range(8):
nx = (dex + dx[d]) % n
ny = (dey + dy[d]) % m
# 공격 포탑은 제외
if nx == ax and ny == ay: continue
game_map[nx][ny] -= point // 2
attack[nx][ny] = True
def break_check():
for i in range(n):
for j in range(m):
if game_map[i][j] < 0:
game_map[i][j] = 0
def max_check():
return max([max(line) for line in game_map])
def maintain_turret():
turret = []
turret_cnt = 0
for i in range(n):
for j in range(m):
# 포탑이 부서진 경우
if game_map[i][j] == 0:
continue
turret_cnt += 1
# 공격과 관련이 있는 경우
if attack[i][j]: continue
turret.append([i,j])
if turret_cnt == 1:
print(max_check())
exit(0)
for i, j in turret:
game_map[i][j] += 1
turret = []
time = 1
for kk in range(k):
# print(kk)
attack = [[0] * m for _ in range(n) ]
ax, ay = select_attack(game_map)
history[ax][ay] = time
time += 1
attack[ax][ay] = 2
dex, dey = select_defense(game_map, ax, ay)
attack[dex][dey] = 2
point = game_map[ax][ay]
if not laser_attack(ax, ay, dex, dey, point):
turret_attack(ax, ay, dex, dey, point)
break_check()
maintain_turret()
print(max_check())
'프로그래밍 > Python' 카테고리의 다른 글
| [프로그래머스] 징검다리 / 이진 탐색 / python (0) | 2024.03.07 |
|---|---|
| [프로그래머스] 입국심사 / 이진 탐색 / python (0) | 2024.02.14 |
| [백준] 233288번 / 주사위 굴리기 2 / 파이썬(Python) (1) | 2023.10.30 |
| [백준] 21611번 / 마법사 상어와 블리자드 / 파이썬(Python) (0) | 2023.10.26 |
| [백준] 21610번 / 마법사 상어와 비바라기 / 파이썬(Python) (0) | 2023.10.26 |
댓글