[2023 삼성 코딩테스트 상반기 오전 1번] 코드트리 - 포탑부수기 파이썬 리뷰 2회차 대각선 탐색
포탑부수기 2회차다~!
이제는 come 배열 구현하는것도 익숙해졌다. (굿~)
배열밖으로 넘어가는경우도 (n+x+dxs[i])%n 으로 처리해주면 문제없이 됐엇다.(외웠던것 ㅋㅋ)
레이저가 가능하냐 안하냐는 역시 visited 로 비교했고..
이번에는 내가 sort(key=lambda x:(x[0])..)로 엄청난 짓했던 것과는 다르게,
2차원배열 대각선 탐색을 사용했다.
공격력이 가장 작은, 가장 큰 포탑을 찾으며
공격자, 피공격자 포탑을 찾는데 여기서
중요한게 그냥 대각선 탐색을 하면되는게아니라, 최근에 공격했나, 안했나를 저장해 놓은 다음에 비교해야하는게 필요했다.
즉, 대각으로 탐색하다가 공격력이 큰놈을 만나면 그놈으로 정보를 업데이트 하고,
만약 공격력이 같은애를 만났으면 최근에 공격했나 안했나를 체크해서,
최근공격or오래공격에 조건에 따라 그놈으로 정보를 업데이트 해줘야했다.
먼저
대각선은 위와같이 총 7번을 탐색하고 해당방향처럼 읽어 나가야
발견됐을때 행+열이 가장 크고, 열값이 가장 큰 값을 잡을 수 있다.
탐색할때, 배열 바깥으로 나가는건 continue 처리를 해줘야하는데 왜냐하면
아래와같이 탐색하기 때문이다.
열의 개수대로 내려가면서 대각 방향으로 줄어드는데
sums 는 행+열의 합을 생각하면된다.
이걸 깔끔하게 코드로 짜면 아래 처럼 쓸 수 있다.
만약에 저런 행+열 최대, 열값 관련 최대값을 바로잡는 알고리즘을 말하면
아래와같은 코드를 사용해보자.
|
maps=[ [16,14,11,7],
[15,12,8,4],
[13,9,5,2],
[10,6,3,1]]
n,m= 4,4
for sum in range(n+m-2,-1,-1) : #대각선의개수
for j in range(m-1,-1,-1) : # 열은 4개니까
i = sum-j #
if (0 > i or i >= n) or (j < 0 or j >= n) : continue
print(maps[i][j],end=' ')
|
그다음 come 테크닉을 써줘서 바로 레이저 경로를 구할 수있었고,
이문제는 역시 국어 수듄 문제가 제일컸던거같다.
문제 조건에 보면,
1. 포탑 개수가 1개 면 바로 종료한다.
2. 최근공격했나안했나 관리해주는 배열 필요 ( 라운드로 관리해주기 )
1번 문제를 모르고있어서 계속 시간초과랑 while 문이 돌길래.. 뭐가 문제가 했더니..
포탑 체크를 안해서 계속 스스로를 공격자로 찾고 피공격자를 못찾고있던거였다..
피공격자를 못찾을경우 -1,-1 의 좌표를 가지는데, 이게 또 -1,-1 일때 끝나게 처리를 안해놔서
[-1][-1] = > [n-1][n-1] 느낌으로 처리돼서 계속 허공에 쏘고있던거였다.
꼭 삼성문제를 풀때
어디를 구현할때 주의해야할껄 주석으로 반드시 적어놔야겠다.
|
import sys
from collections import deque
sys.stdin = open("input_photap1.txt",'r')
deb =0
n,m,k = map(int,input().split())
maps=[list(map(int,input().split())) for _ in range(n)]
round_tower = [ [0]* m for _ in range(n)]
answer=0
attack_add_power = n+m
apayo = [ [False]*m for _ in range(n)]
def in_range(x,y) :
return 0<=x<n and 0<= y < m
def find_attacker(round):
global maps
mini_tower_power = 9000
mini_x,mini_y=-1,-1
recent_round = 0
#이거 블로그 글써서 다시 머리속으로 그려보기.
for sum in range(n + m - 2, -1, -1): # 이건 대각선으로 갈랐을때 경우의수
for j in range(m - 1, -1, -1): #이건 대각선 탐색
i = sum - j
if not in_range(i,j) : continue
if mini_tower_power > maps[i][j] and maps[i][j] > 0: # 어 원래놈보다 더작네?
#바로 언제공격했나 업그레이드
recent_round = round_tower[i][j]
mini_tower_power = maps[i][j]
mini_x,mini_y = i,j
elif mini_tower_power == maps[i][j] and maps[i][j]>0 : #같은놈은 라운드 가장 높은놈으로
if round_tower[i][j] > recent_round:
recent_round = round_tower[i][j] #최근라운드 0으로 해서 다시 최대값애들을 찾아야한다.
mini_x,mini_y = i,j
maps[mini_x][mini_y] += attack_add_power
return mini_x,mini_y
def attacker_attack(ax,ay): # 공격받는애 찾기
global maps
max_tower_power= 0
max_x,max_y = -1,-1
old_round = 1000
for sum in range(0,n + m - 1): # 이건 대각선으로 갈랐을때 경우의수
for j in range(0, m): #이건 대각선 탐색
i = sum - j
if not in_range(i,j) : continue
if i ==ax and j == ay : continue
if max_tower_power < maps[i][j] and maps[i][j] > 0 :
old_round = round_tower[i][j]
max_tower_power = maps[i][j]
max_x,max_y=i,j
elif max_tower_power == maps[i][j] and maps[i][j] > 0 :
if round_tower[i][j] < old_round:#가장 오래된 라운드여야한다.
old_round = round_tower[i][j]
max_x,max_y=i,j
return max_x,max_y
def lazer_attack(ax,ay,bx,by) :
attack_power = maps[ax][ay]
half_attack_power = attack_power//2
#우하좌상
dxs=[0,1,0,-1]
dys=[1,0,-1,0]
queue = deque()
visited = [ [False]*m for _ in range(n)]
visited[ax][ay] = True
queue.append((ax,ay))
come = [ [None]*m for _ in range(n)]
while queue :
x,y = queue.popleft()
for i in range(4):
nx,ny = x+dxs[i],y+dys[i]
if in_range(nx,ny) :
if visited[nx][ny] == False and maps[nx][ny] != 0 :
queue.append((nx,ny))
visited[nx][ny] = True
come[nx][ny] = (x,y)
else :
nx,ny = (n+nx)%n,(m+ny)%m
if visited[nx][ny] == False and maps[nx][ny] != 0 :
queue.append((nx,ny))
visited[nx][ny] = True
come[nx][ny] = (x,y)
if deb:
print(visited)
print(come)
if not visited[bx][by] :
return False
else :
#만약 레이저 어택이 된다면?
maps[bx][by] -= attack_power
a,b = bx,by
while not (a ==ax and b == ay) :
(a,b) = come[a][b]
if a==ax and b == ay : continue
maps[a][b] -= half_attack_power
apayo[a][b] = True
apayo[ax][ay]=True
apayo[bx][by]=True
return True
def bomb_attack(ax,ay,bx,by):
attack_power = maps[ax][ay]
half_attack_power = attack_power//2
ddx=[-1,-1,-1,0,0,1,1,1]
ddy=[-1,0,1,-1,1,-1,0,1]
x,y = bx,by
for i in range(8) :
nx,ny=x+ddx[i],y+ddy[i]
if nx == ax and ny == ay : continue # 공격포탑은못때리게
if in_range(nx,ny) :
if maps[nx][ny] > 0 :
maps[nx][ny] -= half_attack_power
apayo[nx][ny] = True
else :
nx,ny=(n+nx)%n,(m+ny)%m
if nx == ax and ny == ay : continue # 공격포탑은못때리게
if maps[nx][ny] > 0 :
maps[nx][ny] -= half_attack_power
apayo[nx][ny] = True
maps[bx][by] -= attack_power
apayo[ax][ay]=True
apayo[bx][by]=True
return
def break_towers():
for i in range(n):
for j in range(m) :
if maps[i][j] < 0 :
maps[i][j] = 0
return
def repair_tower():
global apayo
for i in range(n) :
for j in range(m) :
if not apayo[i][j] and maps[i][j] != 0 :
maps[i][j] += 1
apayo= [ [False]*m for _ in range(n)]
return
def find_powerful_tower():
max_power = 0
for i in range(n) :
for j in range(m) :
max_power= max(max_power,maps[i][j])
return max_power
def count_tower() :
cnt = 0
for i in range(n) :
for j in range(m) :
if maps[i][j] !=0 :
cnt += 1
if cnt <= 1 :
return True
else :
return False
for tc in range(k) :
ax,ay = find_attacker(tc)
#공격자가 이번 라운드때 공격햇다고 표시
round_tower[ax][ay] = tc+1
bx,by = attacker_attack(ax,ay)
if lazer_attack(ax,ay,bx,by) :
pass#그대로 레이저 어택
else :
bomb_attack(ax,ay,bx,by)
break_towers()
repair_tower()
if count_tower() :
break
answer =find_powerful_tower()
print(answer)
|