[코드트리 챌린지] [2023 삼성 코딩테스트 하반기 오후 1번] 코드트리 - 루돌프의 반란
코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
하하 하반기 삼성 오후1번이다.
결론부터 말하면 삼성코테는 떨어졌다.
하지만 집에 도착해서 다시 풀어봤다.
이문제를 풀면서 어려운점은 아래와같았다.
솔직히 국어문제 빨이 너무 컷던거같은데..
구현하면서 겪은 문제 , 문제 이해 문제를 표시하겠다.
- 문제 이해 문제
1. 처음 산타 번호가 주어질때, 주어지는 순서가 산타의 번호인가? - 실제 삼성에서는 테스트케이스 통과 전부 됐었음.
2. 산타들이 순서대로 이동하고, 이동하지 않은 산타가 있는 자리에 가지 못하는데, 전부다 이동한 다음 충돌을 체크하는지, 아니면 산타가 움직일때마다 충돌을 체크하는지
- 구현하면서 겪은문제
1. 밀린 산타의 영향을 계속해서 받는 처리
2. 루돌프와 가장 가까운 산타를 고르는 알고리즘?
2-1. 루돌프가 산타를 고를때, 대각방향도 거리가 1이면, 대각방향이랑 바로 옆이랑 거리를 둘다 1로 봐야하는가?
3. 바깥으로 떨어졌을때의 처리
4. 루돌프가 산타와 충돌할때, 산타가 루돌프와 충돌할때 해당방향으로 날아가는 방법(?)
1. 처음 산타 번호가 주어질때, 주어지는 순서가 산타의 번호인가? - 실제 삼성에서는 테스트케이스 통과 전부 됐었음.
이부분은 사실 예외적으로 간과할 수 있는 부분이다.
실제 삼성에서는 TC10번까지 전혀 문제 없이 주어진 순서대로가 산타의 번호여서 문제가 안됐다고한다.
그런데 이상하게 이문제를 잘보면
1번부터 P번까지를 꼭 언급 하는것이다.
대게 이런 bfs,2차원배열 구현문제에서 배열위에있는 체스말(?)같은 사람을 하나하나 저장할 필요가 크게 없는 문제가 많다. ( 같은곳에 올라 갔을 경우도 그냥 숫자로 땡처리 하거나 함 )
그런데 이건 굳이 순서를 산타에게 매기고, 그 순서대로 산타가 움직이기 때문에
처음에 번호가 주어진다면 꼭 의심하고, 그 번호를 기준으로 배열의 순서를 매기기 바란다.
나역시도 처음엔 의심하지 않다가 TC에서 막히는걸 보니, append로 들어오는 순서대로 배열을 매겼었다.(나도 TC10번 까지 내고 몰랐겠지..)
2. 산타들이 순서대로 이동하고, 이동하지 않은 산타가 있는 자리에 가지 못하는데,
전부다 이동한 다음 충돌을 체크하는지, 아니면 산타가 움직일때마다 충돌을 체크하는지
이거는 상당한 국어(?)랄까 뭔가 설명을 알아 듣기 어려웠던 문제다.
그도 그럴것이, 설명 조건에 산타와 루돌프가 같은칸에 있게 되면 충돌이 발생한다고 나와있는데
이게 산타들이 모든 움직임을 끝내고 충돌이 발생하는지,
아니면 산타가 1명 움직이자마자 바로 그자리에 루돌프가 있으면 충돌 체크를 하는지
이걸 알기가 힘들었다.
정답은 후자였고,
산타가 움직일때마다 충돌체크를 해줬어야했다.
이부분에서 나도 수행시간이 굉장히 오래걸렸던 부분이다. 만약 다시만든다면
이동하고 루돌프와 같은자리인지 배열을 전부다 탐색하는데,
산타가 이동한다음 루돌프가 있는 자리인걸안다면, 그 산타의 번호를 함수에 넣어서 충돌 처리를 했을것이다. 그러면 훨씬 시간이 줄어들겠지?
1. 밀린 산타의 영향을 계속해서 받는 처리
이부분은 구현하면서 이생각이 들었다.
' 아.. 어렵다.. 와.. 이거 뭐지? 어떻게 짜야하지? '
이생각이들었다.
대충 재귀함수나 while 문같이 반복되다가 해당 조건이 아닐때 while 문을 break 시켜야하는데
이걸... 산타가 산타끼리 중첩되지 않을때마다 체크해야하는데.. 그러면
매번 배열을 들여다 봐야하나.? 산타의 수는 30이라서 시간복잡도가 문제가 안되려나?
이런생각을 했다.
실제 이걸 구현하면서 안좋은 구현방법은 다 가져다가 쓴것같다.
while possible :
해놓고
if ? :
break
이런 조건문 넣어서
while 에서 몇번이고 돌았는지 원..
그래서
while possible :
pandan,idx = santa_same_chk(idx):
if pandan :
continue
else :
break
이런식으로 산타가 같은 자리에 있으면 계속 체크하게 하고 idx가 나온놈을 다시 santa_same_chk 해주면서 비교시켰다.
좀더 나은 방법을 생각했다면 ,
그녀석이 이동한 자리를 return 해서 그곳에 같은놈이 있는지만 체크하고 없으면 넘어가게 했다면 시간복잡도를 훨씬 줄일 수 있었을것..
2. 루돌프와 가장 가까운 산타를 고르는 알고리즘?
2-1. 루돌프가 산타를 고를때, 대각방향도 거리가 1이면, 대각방향이랑 바로 옆이랑 거리를 둘다 1로 봐야하는가?
이게 가장 헷갈린것중에 하나다.
대각방향도 거리1이라고 해서 루돌프가 움직인다고 했는데,
두 지점의 거리를 비교하는식은 abs(x1-x2)**2+abs(y1-y2)**2 이다. 그렇다면,
0 0 0
0 x 0
0 y 0
와
0 0 0
0 x 0
0 0 y
의 거리를 비교하면
위 그림은 거리가 1이고 아래는 거리가 2다.
나는 이때 거리가 1이니까 아래 거리가 2가 나올때 거리 1로 해서 쭉 정렬 시켰다.
여기서 사용한게 코드트리 선생님이 알려준 튜플비교. 진짜 미쳣다...
if ( a, b, -c ) > (da,db,-dc)
이렇게 비교를 한다면,
a의 최대값 비교하고 a가 같다면
b의 최대값 비교하며 b가 같다면
c의 최소값을 비교한다.
이걸사용하면 그 미친 if 문 퍼레이드 else 예외처리를 안해도 되고 매우 깔끔하게 코드를 쓸수있다.
진짜 코드트리선생님.........최고다 엉..근데 엉엏으헝... ㅠㅠ 반년더 부탁합니다
무튼 저런 비교로 행이 가장크고 열이 가장큰 순으로 쭉 순회해서 가장큰놈의 idx와 x,y좌표를 뽑아줬다.
그 x,y좌표를 향해 움직여야 하기때문에 거리가 줄어드는 방향으로 dx,dy테크닉을 사용했다.
3. 바깥으로 떨어졌을때의 처리
바깥으로 떨어졌을땐 -100,-100 으로 산타들의 좌표를 다 보내주고,
만약 산타좌표를 가져올때 if x == -100 and y == -100 : continue
이런식으로 예외처리를 꼭해줘야 했다.
4. 루돌프가 산타와 충돌할때, 산타가 루돌프와 충돌할때 해당방향으로 날아가는 방법(?)
루돌프의 방향을 항상 roo_d 로 저장해 놓았다.
그래서 루돌프와 충돌한다면
check 판단자를 사용해서
if check == ROODOLF :
루돌프가 산타에 충돌했을때 구현
elif check == SANTA :
산타가 루돌프에 충돌했을때 구현
이런식으로 나눠줬다.
santa는 산타의 방향인덱스를 만들어서 그곳에 산타의 방향을 항상 넣어줬다.
결론적으로 이문제는 다푸는데 3시간45분? 정도 걸렸던거같다.
만약 내가 현장에서 봤으면 2시간정도만보고 TC10번만 통과했을지도 모른다.
오후2번문제를봤는데.. 내가 과연풀수있을까 의문이 든다. 세상에 플레티넘 3레벨의 문제가 등장하다니 ㅋㅋ
점점시간이 지날수록 문제가 어려워져서.. 휴 ㅠㅠ 최대한 빨리 붙어서 들어가는게 이득이라고 생각한다.
안정적으로 1번문제들을 100%솔 할 수있을가.. 그냥 의심하지말고 계속하는수밖에..
|
import sys
sys.stdin = open('input_1.txt','r')
n,m,p,c,d = map(int,input().split())
santa= [(-100,-100) for _ in range(p+1)]
deb =0
arr_roo = [ [0]*n for _ in range(n)]
arr_2nd_santa = [ [0]*n for _ in range(n)]
santa_break = [0*n for _ in range(p+1) ]
#산타가 현재 tc 이후에 움직일수있음.
dxs=[-1,-1, 0, 1, 1, 1, 0,-1]
dys=[ 0, 1, 1, 1, 0,-1,-1,-1]
ddx=[-1,0,1,0]
ddy=[0,1,0,-1]
roo_x,roo_y = map(int,input().split())
santa_point = [0 for _ in range(p+1)]
santa_dir = [0 for _ in range(p+1)]
roo_x -=1
roo_y -=1
arr_roo[roo_x][roo_y] = 1
roo_d = 0 #루돌프의 방향
SANTA = 0
ROODOLF = 1
for i in range(p) :
snum, sr,sc = map(int,input().split())
sr-=1
sc-=1
santa[snum]=((sr,sc))
santa_point[snum]=0
santa_break[snum] = 0
arr_2nd_santa[sr][sc] = snum
santa_dir[snum]=-1 #방향없음
def in_range(x,y) :
return 0<=x<n and 0<=y<n
def cal_guri(r1,c1,r2,c2) :
return (r1-r2)**2 + (c1-c2)**2
def is_santa_alive():
#모든 산타배열중 하나라도 나간게 아니면 True
for r,c in santa :
if not (r== -100 and c == -100) :
return True
return False
def roo_santa_short():
max_x,max_y=-1,-1
min_guri = 10000
santa_num = -1
for idx,(i,j) in enumerate(santa) :
if i == -100 and j == -100 : continue
guri = cal_guri(i,j,roo_x,roo_y)
#if guri == 1 :
# guri = 2
if (-guri,i,j) > (-min_guri,max_x,max_y) :
max_x,max_y,min_guri,santa_num=i,j,guri,idx
return santa_num,min_guri
def roodolf_move(tc):
global roo_x,roo_y,roo_d
num_santa,min_guri = roo_santa_short()
santa_x,santa_y = santa[num_santa]
x,y = roo_x,roo_y
for i in range(8) :
nx,ny = x+dxs[i],y+dys[i]
new_guri = (santa_x-nx)**2 + (santa_y-ny)**2
if in_range(nx,ny) and min_guri > new_guri:
roo_x,roo_y = nx,ny
roo_d = i
min_guri = new_guri
if deb:
print(roo_x,roo_y,roo_d)
roodolf_up()
hit_check(tc,ROODOLF)
return
def roodolf_up():
temp_arr = [ [0]*n for _ in range(n)]
temp_arr[roo_x][roo_y] = 1
for i in range(n) :
for j in range(n) :
arr_roo[i][j] = temp_arr[i][j]
return
def santa_move(tc) :
for i in range(1,p+1) :
s_status = santa_break[i]
sr,sc = santa[i]
if sr == -100 or sc == - 100 : # 우주밖으로 나간놈이면?
continue
arr_2nd_santa[sr][sc] = 0
if s_status <= tc : # 그러면 움직일수있다.
guri = cal_guri(sr,sc,roo_x,roo_y)
next_num =-1
for num in range(4) :
nx,ny = sr+ddx[num],sc+ddy[num]
new_guri = cal_guri(nx,ny,roo_x,roo_y)
if in_range(nx,ny) and guri > new_guri and arr_2nd_santa[nx][ny] == 0:
guri = new_guri
next_num = num
if next_num == -1 :
nnx,nny = sr ,sc
else :
nnx,nny = sr+ddx[next_num],sc+ddy[next_num]
santa[i] = (nnx,nny)
santa_dir[i] = next_num
arr_2nd_santa[nnx][nny] = i
#next_arr_2nd[nnx][nny] = (i)
else :
arr_2nd_santa[sr][sc] = i
#next_arr_2nd[sr][sc] = i
continue
hit_check(tc,0)
#for i in range(n) :
# for j in range(n) :
# arr_2nd_santa[i][j] = next_arr_2nd[i][j]
return
def hit_check(tc,case):
# case 가 1일때는 루돌프가 움직
# case 가 0 일때는 산타가 움직
for idx,(sr,sc) in enumerate(santa):
if roo_x == sr and roo_y == sc :
arr_2nd_santa[sr][sc] = 0
# 충돌 후 기절했으면,
santa_break[idx] = tc+2
if case == ROODOLF :
nx,ny = sr+c*dxs[roo_d],sc+c*dys[roo_d]
if in_range(nx,ny) :
sr,sc = nx,ny
arr_2nd_santa[sr][sc] = idx
possible = True
else :
possible = False
sr,sc = -100,-100
santa_point[idx] += c
santa_dir[idx] = roo_d
santa[idx] = sr,sc
#밀려 나간 다음 연쇄적으로 밀려 나가게 반복해야한다.
next_idx = idx
while possible :
next_idx = check_after_hit(next_idx,ROODOLF)
if next_idx == -100 :
break
#산타가 이동했을때 부딫힘
elif case == SANTA :
num = santa_dir[idx]
num = (num +2 )%4
nx,ny = sr+d*ddx[num],sc+d*ddy[num]
if in_range(nx,ny) :
sr,sc = nx,ny
arr_2nd_santa[sr][sc] = (idx)
else : # 나가버리면
sr,sc=-100,-100
santa_point[idx] += d
santa_dir[idx] = num
santa[idx] = sr,sc
#밀려 나간 다음 연쇄적으로 밀려 나가게 반복해야한다.
possible = True
next_idx = idx
while possible :
next_idx = check_after_hit(next_idx,SANTA)
if next_idx == -100 :
break
return
def check_after_hit(idx,check):
# case 가 1일때는 루돌프가 움직
# case 가 0 일때는 산타가 움직
moved_x,moved_y = santa[idx]
mnum = santa_dir[idx]
for idx1,(sr,sc) in enumerate(santa) :
if idx1 == 0 : continue
if sr == -100 and sc == - 100 : continue
if idx1 == idx : continue
if sr == moved_x and sc == moved_y :
if check == SANTA:
nx,ny = sr+ddx[mnum],sc+ddy[mnum] # 1칸씩 이동함
elif check == ROODOLF :
nx,ny = sr+dxs[mnum],sc+dys[mnum]
if in_range(nx,ny) :
santa[idx1] = (nx,ny)
santa_dir[idx1] = mnum
arr_2nd_santa[nx][ny] = (idx1)
else :
santa[idx1] = (-100,-100)
after_idx = idx1
return after_idx
#만약 아무것도 중첩되는게 없으면? -100 리턴
return -100
def heal_santa():
for idx,(sr,sc) in enumerate(santa):
if sr == - 100 and sc == -100:
continue
santa_point[idx] += 1
return
for tc in range(m) :
if not is_santa_alive() :
break
roodolf_move(tc)
santa_move(tc)
heal_santa()
cnt = 0
for items in santa_point:
cnt += 1
if cnt == 1 :
continue
print(items,end=' ')
|