[코드트리 챌린지] [2023 삼성 코딩테스트 하반기 오전 1번] 코드트리 - 왕실의 기사 대결 - 파이썬 리뷰
흠.. 거의 반쯤 찍은느낌으로 hashmap문제를 맞췄다.
뭔가 이해가 덜된상태로 맞춘것같아서 나중에 체크리스트에 넣어놨다. 다시 보고 공부해야지.
그래도 뭔가 블로그 챌린지하면서 점수가 서서히 오르는것같아서 기분이 좋다.
반대로는 떨어질까봐 무섭다 !!!!!!!!!!!!
오늘의 문제는
코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
2023 하반기 삼성 코딩테스트 오전 1번이다.
골드3 수준이여서 뭔가 쉬울줄 알았는데
어떻게 해야하지..? 싶은 떄가 있엇고
그부분을 해결하고 나니 엥? 생각외로 금방 풀렸다.
오후1번하고 비교하면 난이도 차이가 거의 1.5~2배 정도 나는거같다.
나도 오전 1번문제 100% 풀었으면 붙었을지도..?
근데 TC38번에서 막혀서 틀린채로 냈을수도있다.
이문제를 풀면서 막혔던 부분은
1. 기사들이 밀리는걸 bfs를 활용할것이냐 dx,dy테크닉을 활용할 것이냐?
2. 사라진 기사들 처리
1. 기사들이 밀리는걸 bfs를 활용할것이냐 dx,dy테크닉을 활용할 것이냐
사실...이건좀 어거지로 컨닝처럼(?) 푼거같다.
처음에 생각난건 dx,dy테크닉밖에없었다. 결국 bfs나 비슷하지만
방법은, 입력받은 기사를 해당 방향으로 이동시키고, 이동시키는건 temp배열로 한다.
그다음 이동한 temp배열 안에 기사의 정보(1이상의 숫자) 가 있으면 , 그녀석들도 똑같이 이동시키고,
마지막에 0 이 나올때 까지 반복시킨다. -> 이렇게 하려면 재귀함수를 써야하나? 고민했다.
아니면 while 문을 써서 밖에 나가게 된다면 끝내는 possible 판단자를 False 로 바꾼다던지..
근데 bfs를 굳이굳이 쓴다면 어떻게 할 수 있을까?
bfs의 queue 에 기사 좌표를 넣고 해당방향으로 bfs를 하고, 만약에 다른 번호가 나온다면, 그 다른번호의 위치정보를 queue 에다가 넣어준다.
그다음 그녀석들이 또 이동하다가 새로운걸 발견하면 큐에 넣어주고 방향을 계속 보는것.
그러다가 벽을 발견한다면 그냥 그대로 이동할수없는 판단자를 return 해버린다.
2. 사라진 기사들 처리
사라진 기사들 처리는 그냥 isdienight에다가 넣어두고, 해당 번호가 true 라면 명령, 그리고 움직이지 않은놈들을 2차원 이동배열에 넣는걸 실행하지 않게 했다.
위에 이동배열에 넣지않는걸 까먹고 안해서 TC38번에서 막혔다.
하나 움직이지 않은놈들을 구현한건
1~n까지 기사를 for문으로 순회하고,
can_move 라는 움직엿던 기사들 번호 안에 들어있지않으면,
그대로 그상태를 2차원 기사들 배열에 넣게 해서 구현했다. 이거 단순해보이는데 막상 어라? 어떻게해야하지 했엇다. . ㅋㅋ
코테 일주일 쉬엇다고 이정도로 감죽어버리는거 오바잖아..
내년 상반기도 봐야지 아직 6개월이나 남았는데..
어떻게 해야 코테 실력을 늘릴 수있을까?
고민이 많은 밤이다.
|
import sys
from collections import deque
sys.stdin = open('input_1-1.txt','r')
l,n,q = map(int,input().split())
maps=[list(map(int,input().split())) for _ in range(l)]
# 1이 함정, 2가 벽 ,0 은 빈칸
night = {}
night_health = {}
night_damaged = {}
arr_night = [[0]*l for _ in range(l)]
isdie_night = {}
for num in range(1,n+1) :
zr,zc,zh,zw,zk = map(int,input().split())
zr-=1
zc-=1
#인덱스 1부터 시작
night[num] = (zr,zc,zh,zw)
for i in range(zr,zr+zh) :
for j in range(zc,zc+zw) :
arr_night[i][j] = num
night_health[num]=zk
night_damaged[num] = 0
isdie_night[num] = False
def in_range(x,y) :
return 0<=x<l and 0<=y<l
dxs=[-1,0,1,0]
dys=[0,1,0,-1]
def personal_night_move(ri,rd,arr) :
final_can_move_night = []
final_can_move_night.append(ri)
# bfs써서 아래 방향으로 탐색 해버리기.
queue = deque()
visited = [[0]*l for _ in range(l)]
r,c,h,w = night[ri]
for i in range(r,r+h) :
for j in range(c,c+w) :
queue.append((i,j))
visited[i][j] = 1
while queue :
x,y = queue.popleft()
now_night_number = ri
nx,ny = x+dxs[rd],y+dys[rd]
if in_range(nx,ny) :
if arr_night[nx][ny] != now_night_number and arr_night[nx][ny] != 0 : # 가는곳에 다른애가있다면?
next_night_number = arr_night[nx][ny]
#그녀석의 정보를다 queue에 넣어줘야한다.
if not next_night_number in final_can_move_night :
final_can_move_night.append(next_night_number)
nr,nc,nh,nw = night[next_night_number]
now_night_number = ri
for i in range(nr,nr+nh) :
for j in range(nc,nc+nw) :
queue.append((i,j))
visited[i][j] += 1
elif maps[nx][ny] ==2 and arr_night[nx][ny] == now_night_number : #벽위에 올라가있으면,
continue
elif maps[nx][ny] == 2 :# 벽이있다면?
return []
else : # 벽이라면
return []
return final_can_move_night
def is_night_move(oi,od) :
# 이동할때 체스판 밖도 벽으로 간주한다. 즉, 이동할때 벽밖으로 밀지는 못함.
#해당 기사를 다음 칸으로 밀어버리고, 그 이동한 칸에 각 숫자가 있으면 그놈들을 다 이동시켜야한다.
temp_arr = [[0]*l for _ in range(l) ]
can_move = personal_night_move(oi,od,temp_arr)
#움직일수있는 기사들의 번호를 리턴한다. 만약 길이가 0이면 움직일수없음.
if len(can_move) == 0 :
return False,[]
for night_number in can_move: # 움직여지는놈들 움직이게 하기. 아닌애들도 해야함.
night_can_go(night_number,od,temp_arr)
for nights in range(1,n+1) :
if nights in can_move:
continue
if isdie_night[nights] :continue
stay_night_stand(nights,temp_arr)
#여기에 그자리에 있어야함
for i in range(l) :
for j in range(l) :
arr_night[i][j] = temp_arr[i][j]
return True,can_move
def stay_night_stand(night_number,temp_arr) :
r,c,h,w = night[night_number]
for i in range(r,r+h):
for j in range(c,c+w) :
temp_arr[i][j] = night_number
return
def night_can_go(night_number,direction,temp_arr) :
r,c,h,w = night[night_number]
for i in range(r,r+h):
for j in range(c,c+w) :
nx = i+dxs[direction]
ny = j+dys[direction]
temp_arr[nx][ny] = night_number
night[night_number] = (r+dxs[direction],c+dys[direction],h,w)
return
def check_trap(night_number) :
r,c,h,w = night[night_number]
cnt =0
for i in range(r,r+h):
for j in range(c,c+w) :
if maps[i][j] == 1 :#함정이 있으면
cnt +=1
return cnt
def dienight(night_number) :
r,c,h,w = night[night_number]
for i in range(r,r+h):
for j in range(c,c+w) :
arr_night[i][j] = 0
return
def battle_damage(i,d,moved_arr) :
#i,d 의 위치에있는 함정은 영향받지 않는다.
# moved_arr 는 기사의 번호다. 이녀석들이 움직여진 녀석들.
for night_number in moved_arr:
if i == night_number: continue
damage = check_trap(night_number)
night_health[night_number] = night_health[night_number] - damage
night_damaged[night_number] = night_damaged[night_number] + damage
if night_health[night_number] <= 0 : # 빼고난 다음이 0보다 작으면
dienight(night_number)
isdie_night[night_number] = True
return
def chk_live_night() :
point = 0
for i in range(1,n+1) :
if isdie_night[i] : continue
point += night_damaged[i]
return point
answer = 0
for item in range(q) : #왕의명령
oi,od = map(int,input().split())
if isdie_night[oi] : continue
check,moved_arr = is_night_move(oi,od)
if check:
battle_damage(oi,od,moved_arr)
answer = chk_live_night()
print(answer)
|