문제
풀이
구현 순서 정리 (문제 함수별로 정리)
- 공격자 선정
- 부서지지 않은 포탑 중 가장 약한 포탑이 공격자로 선정
- 가장 약한 포탑 선정 기준 (우선순위 순)
- 공격력이 가장 낮은 포탑
- 가장 최근에 공격한 포탑
- (행+열)의 합이 큰 포탑
- 열 값이 가장 큰 포탑
- 공격자에겐 n+m 만큼 공격력 부여
- 공격대상 선정
- 부서지지 않은 포탑 중 가장 강한 포탑이 공격자로 선정
- 가장 강한 포탑 선정 기준 (우선순위 순)
- 공격력이 가장 높은 포탑
- 공격한 지 가장 오래된 포탑
- (행+열)의 합이 작은 포탑
- 열 값이 가장 작은 포탑
- 공격
- 공격은 레이저공격과 포탑공격 두 가지가 존재
- 모두 다 하는 건 아니고, 레이저 공격을 할 수 없는 경우에만 포탑 공격 진행
- 레이저 공격
- 최단 경로로 공격한다고 하였으니 -> bfs 진행
- 최단 경로가 여러개인 경우 -> 우/하/좌/상 순서로 우선순위를 가짐
- !최종 선택된 최단 경로에 있는 포탑들도 공격 받음! 주의
- 포탄 공격
- 공격 대상 뿐 아니라 인접한 8칸에 존재하는 포탑에도 공격 받음
- 얼만큼 피해를 입는지는 레이저와 동일함
- 공격 대상 : 공격자의 공격력 만큼 피해를 입음
- 경로에 있던 포탑(레이저) or 인접 포탑(포탄) : 공격자의 공격력//2 만큼 피해를 입음
- 공격은 레이저공격과 포탑공격 두 가지가 존재
- 포탑 부서짐
- 공격을 받아 0 이하가 된 포탑은 없어짐
- 포탑 재정비
- (이번 사이클에서) 공격자도 아니고, 공격도 받지 않은 공격과 무관했던 포탄은 공격력 +1 증가
- 1~5까지가 한 사이클임. 포탑이 1개가 되면 그 즉시 중지(break)
- 최종적으로 남아있는 포탑 중 가장 강한 포탑의 공격력을 출력하면 됨
사용한 배열
포탑 정보 board (N x M)
공격 시점 체크 배열 history (N x M) -> 공격 포탑에게 현재 시간 기록
공격 관련 여부 체크 배열 attack (N x M) -> turn 마다 초기화
막혔던 부분
- 가장 최근에 공격한 포탑을 어떻게 저장하는가?
- history 전역 배열을 사용해 공격하는 포탑의 현재 시간을 기록해 둠
- 즉, history 값이 클수록 최근 공격한 포탑, 작을수록 공격한 지 오래된 포탑
- 공격자, 공격대상 선정할 때 (행+열)과 같은 우선순위 로직 어떻게 처리할까?
- 그냥 우선 순위 순서대로 조건을 잘 걸어두면 됨
get_attacker()def get_attacker(): global attacker power = 5001 global attacker ay,ax = attacker for y in range(N): for x in range(M): if board[y][x] == 0: continue if board[y][x] < power: # 우선순위 1 : 공격력이 가장 낮은 포탑 power = board[y][x] ay,ax = y,x elif board[y][x] == power: if history[y][x] > history[ay][ax]: # 우선순위 2 : 가장 최근에 공격한 포탑 ay,ax=y,x elif history[y][x] == history[ay][ax]: if y+x > ay+ax: # 우선 순위 3 : (행+열)의 합이 큰 포탑 ay,ax=y,x elif x + y == ax + ay: # 우선 순위 4: 열 값이 가장 큰 포탑 if x > ax: ay,ax=y,x attacker=(ay,ax)- 원래는 가능한 후보들을
candidate라는 배열에 저장해두고 lambda로 정렬 조건 걸어서 진행했는데 이 방식은 부가적으로 처리해야하는 코드가 있어서 실수가능성이 더 큰 것 같음. 따라서 위와 같은 직관적인 방식을 잘 사용하는 게 나을 듯- 맨 처음 작성한 코드
def get_attacker(): global board,history,attacker MIN=5001 candidate=[] for i in range(len(board)): for j in range(len(board)): if board[i][j]!=0: if MIN>board[i][j]: candidate=[] candidate.append((i,j,history[i][j])) MIN=board[i][j] elif MIN==board[i][j]: candidate.append((i,j,history[i][j])) if len(candidate) >1: candidate.sort(key=lambda x:(-x[2],-(x[0]+x[1]),-x[0])) ay,ax,_=candidate[0] attacker=(ay,ax)
- 막힌 방향 진행 시 반대편으로 나오는건 어떻게 구현하는가?
- 알고보니 낚시왕이나 토끼와 경주같이 벽에서 부딪혀서 방향이 바뀌는게 아니라 그냥 n행(열)과 1행(열)이 연결되어 있다고 생각하면 되므로 별도의 처리가 필요 없었음. 패스
- 최단 경로니까 bfs인 건 알겠으나 움직이는 것에도 우선순위가 있다면 어떻게 처리해야하는가?
- 그냥 우선순위 순서대로 방향을 돌리면 자연히 우선순위에 따라 최단 경로를 찾을 수 있게 됨
- 선택된 경로에 있는 포탑도 공격하려면 경로들의 좌표들도 담고 있어야 해. 어떻게 표현하지?
- 처음엔 visited 배열에 True 값대신 직전 좌표 값을 넣어두려 했는데 방문여부와 좌표 기록을 하나의 배열에서 해결하려니까 너무 복잡해졌음
- 관심사 분리해서 visited는 단순히 방문 여부만 판단하고, 큐에 좌표와 더불어 경로 기록을 위한 배열을 추가로 둠.
- NxM 배열 주의 🥵
- 이건 NxN 배열이라고 혼자 생각하고 디버깅 N시간하고 너무나도 현타와서 적음. 예시가 모두 정사각형이라고 NxN 배열이라고 착각하지 말자. 실제 시험장에선 실수하지 말자. 정확하게 읽고 푸는 게 관건
전체 코드
from collections import deque
import copy
N,M,k=map(int,input().split())
d=[(0,1),(1,0),(0,-1),(-1,0)]
d_8=[(-1,-1),(-1,0),(-1,1),(0,-1),(0,1),(1,-1),(1,0),(1,1)]
board=[]
for _ in range(N):
board.append(list(map(int,input().split())))
history=[[0]*M for _ in range(N)] # 최근 공격 시간 기록
t=1
attacker=(-1,-1)
target=(-1,-1)
def print_board():
global board
for i in range(N):
print(board[i])
print('----')
def get_attacker():
global attacker
power = 5001
global attacker
ay,ax = attacker
for y in range(N):
for x in range(M):
if board[y][x] == 0: continue
if board[y][x] < power:
power = board[y][x]
ay,ax = y,x
elif board[y][x] == power: # 여기서부터는 우선순위 비교 들어감
if history[y][x] > history[ay][ax]:
ay,ax=y,x
elif history[y][x] == history[ay][ax]:
if y+x > ay+ax:
ay,ax=y,x
elif x + y == ax + ay:
if x > ax:
ay,ax=y,x
attacker=(ay,ax)
def get_attack_target():
global history
power = -1
global target
ty,tx=target
for y in range(N):
for x in range(M):
if board[y][x] == 0: continue
if x == ax and y == ay: continue
if board[y][x] > power:
power = board[y][x]
ty,tx=y,x
elif board[y][x] == power:
if history[y][x] < history[ty][tx]:
ty,tx=y,x
elif history[y][x] == history[ty][tx]:
if x + y < tx + ty:
ty,tx=y,x
elif x + y == tx + ty:
if x<tx:
ty,tx=y,x
target=(ty,tx)
def laser_attack():
global attacker,target
ax,ay= attacker
tx,ty=target
'''
경로 체크하기 위해 q 에 리스트 요소 정의
'''
q = deque()
q.append((ax, ay, [])) # x, y, route
visited = [[False] * M for _ in range(N)]
visited[ax][ay] = True
while q:
x, y, route = q.popleft()
for dx,dy in d:
nx = (x + dx) % N
ny = (y + dy) % M
if visited[nx][ny]: continue
if board[nx][ny] == 0: continue
# 타겟에 도달한 경우
if nx == tx and ny == ty:
board[nx][ny] -= point
for rx, ry in route: # 경로 추적
board[rx][ry] -= half_point
attack[rx][ry] = True
return True
# 경로 체크
tmp_route = route[:]
tmp_route.append((nx, ny))
visited[nx][ny] = True
q.append((nx, ny, tmp_route))
# 타겟이 도달하지 못하는 경우
return False
def shell_attack():
global attacker,target
ax,ay=attacker
tx,ty=target
board[tx][ty] -= point
for dx,dy in d_8:
nx = (tx + dx) % N
ny = (ty + dy) % M
if nx == ax and ny == ay: continue
board[nx][ny] -= half_point
attack[nx][ny] = True
def remove_top():
for i in range(N):
for j in range(M):
if board[i][j]<0:
board[i][j]=0
def max_check():
return max([max(line) for line in board])
def maintain_top():
turret = []
turret_cnt = 0
for x in range(N):
for y in range(M):
if board[x][y] == 0: continue
turret_cnt += 1
if attack[x][y]: continue
turret.append((x, y))
if turret_cnt == 1:
print(max_check())
exit(0)
for x, y in turret:
board[x][y] += 1
for i in range(k):
attack = [[0] * M for _ in range(N)]
# print_board()
get_attacker()
ay,ax=attacker
attack[ay][ax]=1
history[ay][ax]=t
t += 1
board[ay][ax]+=(N+M)
# print('공격자',attacker)
get_attack_target()
ty, tx = target
attack[ty][tx] = 1
# print_board()
# print('공격대상',target)
point = board[ay][ax]
half_point = point // 2
if not laser_attack():
shell_attack()
# print_board()
remove_top()
# print_board()
maintain_top()
# print_board()
# print('1 turn 완료')
print(max_check())결론
조금 더 명확하고 자세히 읽기. 설계하고 함수 고민하는 데 충분한 시간을 쏟자. 문장 그대로 구현하려고 노력하기. 삼성 문제에서 함수는 쪼개면 쪼갤수록 좋다.
둔한 붓이 총명함을 이긴다