url: https://www.codetree.ai/training-field/frequent-problems/problems/destroy-the-turret/description?page=1&pageSize=20
푼시간 : 대충 4시간..?
from collections import deque
import copy
import heapq as hq
# 설계 10분
N, M, K = map(int, input().split())
castle = [list(map(int, input().split())) for _ in range(N)]
# 공격한 포탑
attack = deque()
victim = []
# 종료조건
def check_end():
cnt = 0
for i in range(N):
for j in range(M):
if castle[i][j] != 0:
cnt += 1
if cnt == 1:
return True
return False
# 가장 약한 포탑찾기
def find_weak():
weak = 10 ** 10
weak_loc = []
for i in range(N):
for j in range(M):
if castle[i][j] == 0: continue
if weak > castle[i][j]:
weak_loc = [[i, j]]
weak = castle[i][j]
elif weak == castle[i][j]:
weak_loc.append([i, j])
max_idx = len(attack)
# 최근 공격
# 공격력 평가
if len(weak_loc) > 1:
for yl, xl in weak_loc:
if [yl, xl] in attack:
idx = attack.index([yl, xl])
max_idx = min(max_idx, idx)
# 행과 열의 합
# 최근 공격 여러개
if max_idx == len(attack):
max_sum = -1
max_idx = []
for yl, xl in weak_loc:
if max_sum < yl + xl:
max_sum = yl + xl
max_idx = [[yl, xl]]
elif max_sum == yl + xl:
max_idx.append([yl, xl])
# 열 값이 가장 큰
# 행과 열 합 max 여러개
if len(max_idx) > 1:
max_idx.sort(key=lambda x: x[1], reverse=True)
return max_idx[0]
else:
return attack[max_idx]
else:
return weak_loc[0]
# 강한 포탑찾기
def find_strong(weak_loc):
strong = -1
strong_loc = []
for i in range(N):
for j in range(M):
if i == weak_loc[0] and j == weak_loc[1]: continue
if castle[i][j] == 0: continue
if strong < castle[i][j]:
strong_loc = [[i, j]]
strong = castle[i][j]
elif strong == castle[i][j]:
strong_loc.append([i, j])
min_idx = -1
old = []
# 가장 오래된 공격
# 공격력 평가
if len(strong_loc) > 1:
for yl, xl in strong_loc:
if [yl, xl] not in attack:
old.append([yl, xl])
else:
idx = attack.index([yl, xl])
min_idx = max(min_idx, idx)
# 행과 열의 합
# 공격 경험이 없음
if len(old) >= 1:
# 1개 이상일 경우
if len(old) > 1:
min_sum = 10 ** 10
min_idx = []
for yl, xl in old:
if min_sum > yl + xl:
min_sum = yl + xl
min_idx = [[yl, xl]]
elif min_sum == yl + xl:
min_idx.append([yl, xl])
# 열 값이 가장 작은
# 행과 열 합 max 여러개
if len(min_idx) > 1:
min_idx.sort(key=lambda x: x[1])
return min_idx[0]
else:
return old[0]
else:
return attack[min_idx]
else:
return strong_loc[0]
X = [1, 0, -1, 0]
Y = [0, 1, 0, -1]
min_len = 10 ** 10
# 최단경로 찾기
def lazer(strong_loc, weak_loc, attack_power):
sy, sx = strong_loc
wy, wx = weak_loc
visited = [[0 for _ in range(M)] for _ in range(N)]
queue = [(wy, wx, [])]
visited[wy][wx] = 1
flag = 0
answer = []
while len(queue) > 0:
yy, xx, q = queue.pop(0)
for _ in range(4):
dy = (yy + Y[_]) % N
dx = (xx + X[_]) % M
if dy == sy and dx == sx:
flag = 1
answer = q
break
if castle[dy][dx] == 0 or visited[dy][dx] == 1: continue
temp_q = q[:]
temp_q.append((dy, dx))
queue.append((dy, dx, temp_q))
visited[yy][xx] = 1
if flag == 1: break
# 이동 불가
if flag == 0:
return False
# 최단 거리 여러개 일 수 없음
castle[sy][sx] = max(0, castle[sy][sx] - attack_power)
victim.append([sy, sx])
# 경로 공격
for mdy, mdx in answer:
victim.append([mdy, mdx])
castle[mdy][mdx] = max(0, castle[mdy][mdx] - (attack_power // 2))
return True
def bomb(attack_power, weak_loc, strong_loc):
Y = [-1, -1, -1, 0, 0, 1, 1, 1]
X = [1, 0, -1, 1, -1, 1, 0, -1]
sy, sx = strong_loc
wy, wx = weak_loc
castle[sy][sx] = max(0, castle[sy][sx] - attack_power)
victim.append([sy, sx])
# 주변 8개 폭파
for _ in range(8):
dy = (sy + Y[_]) % N
dx = (sx + X[_]) % M
# 공격자 제외
if dy == wy and dx == wx: continue
if castle[dy][dx] != 0:
victim.append([dy, dx])
castle[dy][dx] = max(0, castle[dy][dx] - (attack_power // 2))
def arrange():
global victim
for i in range(N):
for j in range(M):
if [i, j] in victim or [i, j] == attack[0]: continue
if castle[i][j] == 0: continue
castle[i][j] += 1
victim = []
def print_castle():
for i in range(N):
print(*castle[i])
for i in range(K):
flag = 0
if check_end():
break
weak_loc = find_weak()
attack.appendleft(weak_loc)
strong_loc = find_strong(weak_loc)
castle[weak_loc[0]][weak_loc[1]] += N + M
attack_power = castle[weak_loc[0]][weak_loc[1]]
flag = lazer(strong_loc, weak_loc, attack_power)
if not flag:
bomb(attack_power, weak_loc, strong_loc)
if check_end():
break
arrange()
result = -1
for i in range(N):
result = max(result, max(castle[i]))
print(result)
진짜 부수고싶은 문제였다. 하지만 풀어냄
느낀점
- 열값이 큰건 y값이 크다는 거^^..
- 가장 약한 포탑을 구할 때는 최신꺼를 구해야함 / 가장 센 포탑을 구할 때는 오래된 거를 구해야함
- deque로 해야함
- 왜냐하면 index함수는 앞에서부터 찾기 때문에 뒤에 append하면 정확한 값을 알 수 없음.
- 따라서 appendleft를 한 뒤 index로 찾아내기. - 또한 index함수는 없을 경우 에러를 터뜨리기에 꼭 if문으로 확인해줘야 함
- 오래된 거를 구할 때 없을 경우만 존재하는 경우/ 없을 경우랑 있는 경우 같이 존재하는 경우/ 있는 경우만 존재하는 경우 총 세가지를 생각해줬어야 함. 왜냐면 없을 경우랑 있는 경우중 없는 경우가 우선순위이기에
- max, min 정말 헷깔려 죽을뻔함 -> 손코딩으로 대충 짜자..
- 전역배열의 경우 copy를 안하면 reset됨!!!
- 나의 경우 백트래킹을 하려고 배열 안에 값을 넣고 재귀돌리고 빼고를 반복했는데 계속 매열이 빈게 나와서 왜대체 왜그러지 했는데 당연히 그럴수밖에 없었음^^ 무조건 copy하자
- '즉시'라는 단어 메모 만개 -> 함수 돌때마다 해당 함수 쑤셔넣기
- 백트래킹은 모든 조합을 구하는 것 -> bfs + 방향 우선순위대로 구하자마자 break하기
Backend Developer