코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
대략 푸는데.. 걸린시간만 합치면.. 15시간 정도 되는것같다. (2일, 빡집중안하고 설렁)
여기서 아주 안좋은 습관 -> 빡집중안하기 인데. 사실 빡집중했어도 4시간안엔 못풀었다는게 함정이다. ..
이문제를 풀고 가장 큰현타는
내가 생각한걸 구현하는데 무려 코드줄수가 369줄인게 레전드...
특히나 저번 문제에서는 주어진대로 그대로 구현해보자 라고 했는데
그 구현을 수학적지식이있으면 매우 쉽게 구현할 수 있었고,
내가 구현할 수 없는 부분도 있었다.
(우하좌상 의 우선순위를 가지는 최단거리 구하기)
이부분은 검색해서 다른분의 풀이를 참고했다.
-> 덕분에 해당 테크닉을 어떻게 하는지 알게됐다.
bfs로 최단거리를 구하고, 그 경로를 가는 방법.
-> visited 처리를 할때 come 같은 행렬을 만들어서 nx,ny 가 어느 x,y에서 왔는지 저장해주고
while 문에서 come[도착지x][도착지y] 에서 쭉 빼주고 시작점x, 시작점y에 도착하면 break 해주고
그 경로 어느 2차원 배열에 저장하면 해당 경로를 저장할 수 있다.
이 문제에서 복잡한것은 사실
+공격하는 포탑 선정, 공격받는 포탑 선정 (구현 or 정렬?)
+레이저 (BFS)
두개라고 생각한다.
나머지 포탄 처리랑 행렬 바깥으로 나갈때 반대편으로 다시 돌아오게 하는처리는
나는 원래 if 문을 사용해서 nx,ny 가 <0 이되면 nx = n-1 이런식으로 했는데
더쉬운 방법이 있었다.
== 행렬이 바깥으로 나갈때 더쉽게 처리하는 방법 ==
nx = (x+dxs[num] + n)%n
ny = (y+dys[num] +m)%m
으로 하면 된다.
만약 예를들어 x+dxs[num]이 -1 이 나왔다 하자, 배열크기는 4고. 그러면
3%4 = 3 이 나온다. x가 -1이 된다면 3이 된다는말. 말그대로 배열 반대편으로 날아가니 성공 !!
기억해두도록 하자.
내가 공격하는 포탑선정, 공격 받는 포탑 선정을 한 방법은
바로 sort(key=lambda x:x[0]) 이 람다 정렬을 사용했다.
문제 조건을 보면 딱 사용하기 좋게 해놓았는데...
내가 어떻게 찾았는지 확인해보자
가장 약한 포탑은 다음의 기준으로 선정됩니다.
- 공격력이 가장 낮은 포탑이 가장 약한 포탑입니다.
- 만약 공격력이 가장 낮은 포탑이 2개 이상이라면, 가장 최근에 공격한 포탑이 가장 약한 포탑입니다. (모든 포탑은 시점 에 모두 공격한 경험이 있다고 가정하겠습니다.)
- 만약 그러한 포탑이 2개 이상이라면, 각 포탑 위치의 행과 열의 합이 가장 큰 포탑이 가장 약한 포탑입니다.
- 만약 그러한 포탑이 2개 이상이라면, 각 포탑 위치의 열 값이 가장 큰 포탑이 가장 약한 포탑입니다.
공격력이 가장 낮은 포탑 -> for문으로 순회해서 가장 낮은 놈들을 배열에 저장한다.
배열 개수가 2 이상이다 -> 최근에 공격한 포탑값을 불러와서 정렬 후 배열에 넣는다.
배열에 넣고 가장 작은 값을 빼고 나머지 요소값과 비교하며 같은놈이 있으면 배열에 넣는다.
배열 개수가 2이상이면 -> 행과 열의 합으로 정렬하고 같은 값이면 배열에 넣는다.
배열 개수가 2 이상이면 -> 열 값으로 정렬하고 가장 작은값을 출력한다. ...
이 과정을 구현을 하다보니 중간중간에 배열 처리나, 정수 이름처리
변수처리가 너무 고역이였다. 물론 처음 만들고
그다음 공격받는 포탑은 반대로 하면되지만....
만약에 내가 잘못 구현했으면 어떡하지? << 가 큰 문제 였고.
이부분을 수학적 지식을 통해 쉽게 구현할 수 있는걸 알았다.
가장최근 공격과 공격력이 낮은 포탑은 for문으로 할수있다고 해도,
행과 열의 합이 가장크고 열값이 가장 작게 순회하며 값을 가져오는 방법은.
[1] [2] [3] [4]
[5] [6] [7] [8]
[9] [10][11][12]
[13][14][15][16]
위 배열이면
위 그림처럼 순회하는 것이다. 이건 어떻게 짤까?
알아 두도록 해보자.
(n-1)+(m-1) 이렇게 이해해보자.. 그래서 range안 값이 저렇게 나오고..
for sum in range(n+m-2,-1,-1): # 각 n+m 을 모두 순회한다.
for j in range(m-1,-1,-1):
i=sum-j
maps[i][j] 값이 위처럼 순회하는데
한번 체크해보자.
n=4,m=4 라고하면
for sum in range(6,-1,-1) : -> 이부분은 대각선의 배열 개수다.
for j in range(3,-1,-1): -> 이부분은 3,2,1,0,으로 줄어드는데
i=sum-j 이다.
sum = 6 일때
i = 6 -3 = 3
i=3,j=3
i=4,j=2
i=5,j=1 ...
sum = 5 일때
i=2 j=3
i=1 j=4
sum값에 따라 대각선으로 순회하고있다. 이건
j값에 따라 i값을 정해주게 하면 구현할 수있을것같은데
for (m-1,-1,-1) < 이걸 생각해 내는데 현장에서 맞딱들였으면 당황했을꺼같다.
그러니까 저런 개 노가다 순회로 풀었겠지...
위 수학지식을 활용하면, in_range(x,y)같은거로 처리해주고,
만약 maps[i][j] == 0 이면 그냥 탐색안하고
최소, 최대값을 한번에 구할 수있게 lastattack[i][j] = 몇번째 순서때 이 포탑이 공격했는지 값을 가짐.
각 포탑 공격력,몇번째순서,행,열 의 값들을 다 받은다음에 최소,최대,최소,최소 형태로 받아서 다 순회해주면 ( 파이썬이 이게 제일 좋다. )
수학지식력으로 위 조건을 구현 할 수 있다.
여기서 내가 6시간 넘게 헤매였던 부분은
저 " 공격한지 가장 오래된 포탑" 의 처리 때문에 실수했엇다.
나는 공격 횟수를 생각해서 공격할때마다 그 포탑에 +1 을 했엇다. 하지만 이런경우,
1,2,3 턴에 a포탑이 공격
4,5 턴에 b포탑이 공격.
a포탑은 3, b포탑은 2... 결국 가장 오래된 포탑이라고 하면 a포탑을 가져와야하는데
b포탑이 요소값이 적으니 b포탑을 가져와서 문제가 났던거였다.
ㄹㅇ 국어때문에 시간 버리니까 현타 개오졋다..
이부분을 해결하니 문제를 풀 수있엇다.
코드트리 센세 정말 감사해요 진자
질문 < 답변 바로해주는것
이것때문에 코드트리 돈내고 든든하게 쓰는이유 1000% 입니다..
백준? SWE? 내가 어려워하는거 누가 질문 바로바로 해줌..?
코드트리는 전담 센세가 친절하게 TC랑 힌트도 갖다주심.. 이것때문에 쓴다 후..
그렇게 공격하는, 공격받는 포탑을 구하면. 나머지는 레이저 부분은 위에서 말한
역추적 테크닉을 사용하면 경로를 2차원배열로 저장 할 수 있고, 그경로에 있으면 1/2의 공격력맞고,
맞는 지점은 원래 공격력을 맞고. 이렇게 배열 처리 해주면 된다.
그리고 이때 맞은놈들을 배열에 저장해서 repair 할때 반영하고, 꼭 반영한다음 맞은놈들 배열을 초기화 해주자.
나같은경우는 lazer 와 bomb 두 trace흔적값을 저장해서 반영했는데
bomb 이후 lazer를 할때 bomb 이 초기화가 안됐어서 제대로 안됐었다. 이거 디버그 하느라 또 시간이 걸림 ..
문제를 풀다보니 몇가지 디버그 테크닉이 생겼는데
1. 조건문 확인
if (조건문) :
조건문이 제대로 되나 안되나 print((조건문)) 을 넣어서 확인해보기 .
2. debug() 함수 만들어서 원할때 보게 하기
이건 좀 호불호가 크게 나뉠꺼같은데 debug가 이쁘게 보이도록 잘 만들어두면 나중에 2시간후에 디버그할때도 너무 유용하게 쓰일것같다.
3. deb 정수 값을 사용해서 그 값이 1이 되면 디버그들 전부 나오게하기.
특히나 이건 마지막에 값을 출력할때 자주 쓰는데 테스트 케이스 하나하나 통과해볼때 아주 유용했다.
if dbg :
debug()
repair()
if dbg:
debug()
이런식으로 해두고 확인하는거다.
dbg 값을 0으로 하면 깔끔히 repair()만 실행되고
dbg 값을 1로 하면 debug()값이 실행되서 디버그를 할 수 있다.
참고로 이건 홈페이지에서 디버그할때인데..
실제 삼성에서는 visual studio 를 사용하고 sys.stdin.readline 등을 사용하니까
지금부터는 vscode와 같이 디버그 환경에서 바로바로 체크할 수 있도록 연습하려고한다.
후 진작에 할껄.. 하지만 코드트리 편집기 사랑해요!!!!!!!!
마지막으로 코드를 올리고 물러나겠다.
|
from collections import deque
n,m,k=map(int,input().split())
deb = 0
maps = [ list(map(int,input().split())) for _ in range(n)]
trace = [ [0]*m for _ in range(n)]
bomb_trace = trace = [ [0]*m for _ in range(n)]
handicap = n+m
#공격한 포탑을 저장한다. 각자 시간에 따라 공격할때 1씩 가지게된다.
recent_attack = [ [0]*m for _ in range(n)]
#처음엔 다 공격햇다고 여겨야하니까 전부다 넣는다.
# 시점 0 처음 공격경험 넣기
def debug():
print('maps:')
for item in maps:
print(*item)
print()
def low_tower():
low_arr = []
low_ans = []
for i in range(n) :
for j in range(m) :
#공격력, 행, 열 저장
if maps[i][j] != 0 :
low_arr.append((maps[i][j],i,j))
low_arr.sort(key=lambda x:x[0])
low_power,_,_ = low_arr[0] # 공격력이 가장 낮다.
for idx in range(len(low_arr)) :
temp_power,temp_x,temp_y = low_arr[idx]
if low_power != temp_power :
break
else :
low_ans.append((temp_power,temp_x,temp_y))
return low_ans
def high_tower():
high_arr = []
high_ans = []
for i in range(n) :
for j in range(m) :
#공격력, 행, 열 저장
if maps[i][j] != 0 :
high_arr.append((maps[i][j],i,j))
high_arr.sort(key=lambda x:-x[0])
high_power,_,_ = high_arr[0] # 공격력이 가장 높다.
for idx in range(len(high_arr)) :
temp_power,temp_x,temp_y = high_arr[idx]
if high_power != temp_power :
break
else :
high_ans.append((temp_power,temp_x,temp_y))
return high_ans
def find_attack():
temp_arr_1 = low_tower()
low_attackers = temp_arr_1.copy()
# 가장 약한 포탑.
weak_x,weak_y = -1,-1
# 공격력 낮은게 2개 이상이라면, 최근 공격한놈
if len(low_attackers) >= 2 :
gajang_chigun = []
for idx1 in range(len(low_attackers)):
(_,recent_x,recent_y) = low_attackers[idx1]
gajang_chigun.append((recent_attack[recent_x][recent_y],recent_x,recent_y))
gajang_chigun.sort(key=lambda x:-x[0]) # 가장 최근에 공격한 포탑.
gajang_temp =[]
recent_atk_count,_,_ = gajang_chigun[0] # 가장 최근 공격했다를 가져온다.
for idx3 in range(len(gajang_chigun)) :
re_ga,re_x,re_y=gajang_chigun[idx3]
if recent_atk_count != re_ga :
break
else :
gajang_temp.append((re_x,re_y))
# 만약 가장 최근에 공격한 포탑이 2개 이상이라면, 행과 열 합 가장큰놈 찾기
if len(gajang_temp) >= 2 :
max_hap=gajang_temp.copy()
max_hap.sort(key=lambda x:-(x[0]+x[1])) # 두개의 합이 가장큰대로
max_hap_x,max_hap_y = max_hap[0] # 두개의 합에서 하나를 꺼내서 차례대로 비교한다.
y_hap= []
for idx2 in range(len(max_hap)): #차례대로 비교하기
temp_hap_x,temp_hap_y = max_hap[idx2]
if (max_hap_x+max_hap_y) != (temp_hap_x+temp_hap_y): # 만약 달라지면 break한다.
break
else:
y_hap.append((temp_hap_x,temp_hap_y))
if len(y_hap) >= 2 : # 행과 열의 합이 가장큰 포탑이 두개 이상이다.
y_hap.sort(key=lambda x:-x[1]) # y값이 가장크게 정렬
weak_x,weak_y= y_hap[0]
else : # 행과열이 가장큰게 하나면 설정
weak_x,weak_y = max_hap_x,max_hap_y
else : # 가장 최근에 공격한 포탑
weak_x,weak_y=gajang_temp[0]
pass
else :
_,weak_x,weak_y = low_attackers[0]
#공격을 수행하기에 +1
return (weak_x,weak_y)
def in_range(x,y) :
return 0<=x<n and 0<= y < n
def finish_chk() :
cnt = 0
for i in range(n) :
for j in range(m):
if maps[i][j] != 0 :
cnt += 1
#print(cnt==1)
if cnt == 1 :
return True
return False
def lazer_attack(x1,y1,x2,y2) :
global trace
trace = [ [0]*m for _ in range(n)]
#우/하/좌/상
dxs=[0,1,0,-1]
dys=[1,0,-1,0]
visited = [ [0]*m for _ in range(n)]
come = [ [None for _ in range(m)] for _ in range(n)]
queue = deque()
queue.append((x1,y1))
num = 0
visited[x1][y1] = 1
trace[x1][y1] = 1
while queue :
x,y = queue.popleft()
for num in range(4):
nx,ny = (x+dxs[num]+n)%n,(y+dys[num]+m)%m
#반대편으로 넘어갔을때 인덱스
if maps[nx][ny] != 0 and visited[nx][ny] == 0 : #nx변환식을 써야한다.
visited[nx][ny] = visited[x][y]+1
come[nx][ny] = (x,y)
queue.append((nx,ny))
if deb == 1 :
print('visited')
for imtes in visited :
print(*imtes)
print('come')
for imtes2 in come :
print(*imtes2)
if not visited[x2][y2] :
return False
x,y = x2,y2
#도착지로부터 시작해서 역으로 경로탐색한다고 생각.
while not (x==x1 and y == y1):
power = maps[x1][y1] // 2
if x == x2 and y == y2 :
power = maps[x1][y1]
maps[x][y] = maps[x][y] - power
trace[x][y] = 1
if maps[x][y] < 0 :
maps[x][y] = 0
x,y = come[x][y]
# 레이저 공격이 안되면 False 리턴
return True
def bomb_attack(x1,y1,x2,y2):
global bomb_trace
bomb_trace = [ [0]*m for _ in range(n)] #초기화
dxs1=[-1,-1,-1, 0,0, 1,1,1]
dys1=[-1, 0, 1,-1,1,-1,0,1]
if deb :
print('bomb go!!',x1,y1,x2,y2)
#직접타격
maps[x2][y2] -= maps[x1][y1]
bomb_trace[x2][y2] = 1
bomb_trace[x1][y1] = 1
if maps[x2][y2] < 0 :
maps[x2][y2] = 0
#근처 타격
for i in range(8) :
nx,ny = x2+dxs1[i],y2+dys1[i]
if (nx) == n :
nx = 0
elif nx == -1 :
nx = n-1
if ny == m :
ny = 0
elif ny == -1 :
ny = m-1
if maps[nx][ny] != 0 and not (nx == x1 and ny == y1):
maps[nx][ny] -= (maps[x1][y1] // 2 )
if maps[nx][ny] < 0 :
maps[nx][ny] = 0
bomb_trace[nx][ny] = 1
return
def attacker_attack():
temp_arr_1 = high_tower()
high_attackers = temp_arr_1.copy()
# 가장 강한 포탑.
power_x,power_y = -1,-1
# 공격력 낮은게 2개 이상이라면, 최근 공격한놈
if len(high_attackers) >= 2 :
gajang_chigun = []
for idx1 in range(len(high_attackers)):
(_,recent_x,recent_y) = high_attackers[idx1]
gajang_chigun.append((recent_attack[recent_x][recent_y],recent_x,recent_y))
gajang_chigun.sort(key=lambda x:x[0]) # 가장 오래전에 공격한 포탑. (공격카운트가 가장낮은)
gajang_temp =[]
recent_atk_count,_,_ = gajang_chigun[0] # 가장 최근 공격했다를 가져온다.
for idx3 in range(len(gajang_chigun)) :
re_ga,re_x,re_y=gajang_chigun[idx3]
if recent_atk_count != re_ga :
break
else :
gajang_temp.append((re_x,re_y))
#print(gajang_temp)
# 만약 가장 최근에 공격한 포탑이 2개 이상이라면, 행과 열 합 가장큰놈 찾기
if len(gajang_temp) >= 2 :
max_hap=gajang_temp.copy()
max_hap.sort(key=lambda x:(x[0]+x[1])) # 두개의 합이 작은
#print(max_hap)
max_hap_x,max_hap_y = max_hap[0] # 두개의 합에서 하나를 꺼내서 차례대로 비교한다.
y_hap= []
for idx2 in range(len(max_hap)): #차례대로 비교하기
temp_hap_x,temp_hap_y = max_hap[idx2]
if (max_hap_x+max_hap_y) != (temp_hap_x+temp_hap_y): # 만약 달라지면 break한다.
break
else:
y_hap.append((temp_hap_x,temp_hap_y))
if len(y_hap) >= 2 : # 행과 열의 합이 가장큰 포탑이 두개 이상이다.
y_hap.sort(key=lambda x:x[1]) # y값이 가장크게 정렬
power_x,power_y= y_hap[0]
else : # 행과열이 가장큰게 하나면 설정
power_x,power_y = max_hap_x,max_hap_y
else : # 가장 최근에 공격한 포탑
power_x,power_y=gajang_temp[0]
pass
else :
_,power_x,power_y = high_attackers[0]
return (power_x,power_y)
def tower_repair(x1,y1,x2,y2):
global trace
global bomb_trace
if deb ==1 :
print('before repair')
for x in maps:
print(*x)
print('trace')
for x1 in trace:
print(*x1)
print('bomb')
for x2 in bomb_trace:
print(*x2)
for i in range(n) :
for j in range(m) :
if deb :
pass
#print('check',i,j)
#print((i == x1 and j == y1) )
#print((i == x2 and j == y2 ))
if (maps[i][j] != 0) and (trace[i][j] == 0) and (bomb_trace[i][j] == 0):
#print(maps[i][j])
maps[i][j] += 1
if deb == 1 :
print('after repair')
for x in maps:
print(*x)
trace = [ [0]*m for _ in range(n)]
bomb_trace = [ [0]*m for _ in range(n)]
return
def find_most_tower():
count =0
for i in range(n) :
for j in range(m):
count = max(count,maps[i][j])
return count
for tc in range(1,k+1) :
if finish_chk() :
break
(attack_start_x,attack_start_y) = find_attack()
(soobi_x,soobi_y) = attacker_attack()
#최근에 공격했다고 배열에 넣어줘야한다.
recent_attack[attack_start_x][attack_start_y] = tc
maps[attack_start_x][attack_start_y] += (n+m)
if deb ==1 :
print('recent_attack')
for jj in recent_attack:
print(*jj)
print('maps')
for jj3 in maps:
print(*jj3)
print(attack_start_x,attack_start_y)
print(soobi_x,soobi_y)
print('before attack')
for sms in maps:
print(*sms)
if not lazer_attack(attack_start_x,attack_start_y,soobi_x,soobi_y) :
bomb_attack(attack_start_x,attack_start_y,soobi_x,soobi_y)
if deb :
print('after attack')
for sms in maps:
print(*sms)
tower_repair(attack_start_x,attack_start_y,soobi_x,soobi_y)
max_answer = find_most_tower()
print(max_answer)
|
'코딩 테스트' 카테고리의 다른 글
| [코드트리] 서로 다른 숫자 = set() 의 사용처 공부 (0) | 2023.09.21 |
|---|---|
| [2022 삼성 코딩테스트 하반기 오후 1번] 코드트리 - 코드트리 빵 (0) | 2023.09.20 |
| [2023 삼성 코딩테스트 상반기 오후 1번] 코드트리 - 메이즈러너 파이썬 풀이 (1) | 2023.09.14 |
| [코드트리 챌린지] K개 중 하나를 N번 선택하기(Simple) / k개 중에 1개를 n번 뽑기 (0) | 2023.09.13 |
| [코드트리 챌린지] 마지막으로 남은숫자 (0) | 2023.09.13 |