[2022 삼성 코딩테스트 하반기 오후 1번] 코드트리 - 코드트리 빵
코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
이 문제는 내가 작년 삼성 하반기를 도전하고 개같이 틀려서 구현에 실패한 문제이다.
테스트 케이스 1번도 통과하지 못했고 그때 당시 막혔던 이유는 bfs를 능수능란하게 사용하지 못했다.
그리고 자료구조도 상당히 애매(?)했는데
이번 풀이 역시도 한 2차원 배열에 전부다 때려 박다가 결국 TC5번, TC98번에서 막혔다.
코드 복기를 하며 유의하게 생각한걸 작성해보겠다.
삼성에서는.. 무슨 텐트 재난 편의점? 이런걸로 시작해서 걸어갔던거 같다.
그때당시에는 사람을 등장시켜서 한번한번 지나가게하는 시뮬레이션을 구현 하지도 못했고
사람을 (x,y) 로 저장해왔는데 어떻게 가져와야하지? 몰라서 튜플도 샘플로 하나하나 되나 확인하고 했던 기억이 난다..
그러니까 떨어지지..
지금 이문제를 풀어보니 구현에는 어렵지 않으나 처음에 자료구조를 이상하게 짜놔서 시간이 오래 걸렸다.
먼저 maps 라는 2차원 배열에 위 조건을 모두다 넣기위해 나는 어떤 짓을했냐면..
최대값을 보니..
아 베이스는 최대 225-30 = 195개 구나!
사람은 최대 30명이구나!
를 알게 되어서...
베이스는 1~200 까지
사람은 1001~1031 까지
편의점은 901~931 까지
만약 움직일 수 없는 경우가 된다면.. 각자 + 10000을 해버리고.
사람은 움직일 수 없으면 out=[] 이라는 배열에 넣어 인덱스를 맞춰서 False,True 로 관리했다. ( 아니 이걸 이렇게 햇으면 나머지도 이렇게 하셔야죠 ; )
그래서 이걸 2차원배열로 보면
[0] [0] [0] [0] [0]
[10001, 1001] [0] [901] [0] [2]
[0] [0] [0] [0] [0]
[0] [3] [0] [902] [0]
[903] [0] [0] [0] [4]
이렇게 나와버린다.
저렇게 10001 이 된게 더이상 지나갈 수 없는 베이스 캠프이고, 901이 1번 사람의 편의점. 1001 이 1번 사람이다..
모든사람이 이동한 다음 편의점을 지나갈수없고 베이스캠프를 지나갈수없는 부분은 큰 문제가 되지않았다(서순문제라)
근데 조금 까다로웠던건 bfs로, 901번 편의점에서 최단경로에 위치한 베이스캠프를 구하는건데
처음에는 그냥 for i in range(4): 해서 단순히 길이가 짧아지는 쪽으로 이동하게 처리했다.
하지만 TC5번에서 걸리게 됐고 만약에 3방이 막혀있고
0200
0120
0203
0000
(0번이동가능,1번 사람, 2번 벽)
1번이 3번으로 이동하려면, 3으로 부터 멀어진다음 빙글 돌아가야한다.
하지만 내가 처음에 구현한 방법은 아무것도 움직이지 않고 그냥 가만히 있게된다.
이래서 시간초과 ( 계속해서 가만히 있어서 변함없음. )가 발생. 이거 다시 bfs로 만드느라 고생했다..
그리고 이전에 Lazer 테크닉을 쓰면서 역탐색 테크닉을 사용하여
목적지로부터 시작지점 까지의 최단거리를 구하고,
그 값을 while x != x1 or y != y1 : 와 같이 계속 뒤로 탐색해서 해당 경로를 아는 방법이 있었다.
여기서는 그것을 사용하여,
come[x][y] == (x1,y1)
x1과y1는 사람의 위치
그러니까 come 배열이 뒤로 가르키는게 시작점이면 이 x,y를 next_x,next_y로 저장하게 했다.
이부분에서 come 에 아무값이 들어가 있지않다고 엄청 에러가 나서 디버깅하는데 3시간이상 썼는데
그이유는,
바로 사방이 전부 막혀있어서 아무곳도 갈수 없을때이다.
근데 문제조건에는 사방히 막혀서 갈수 없는경우는 없다고 하는데
디버깅을 하다보니 무슨 문제인가 보니까..
0 0 902
0 0 1001
0 0 1002
0 0 0
라고 치면, (1001은 사람, 1002도 사람, 902는 1002사람의 편의점)
위로 가야하는데 내가 bfs 조건문에서 0<= maps[nx][ny] < 1000 으로 해놨던것,,,, ;;;
그래서 이부분을 최대 사람수까지 < 1031 로 처리해주니까
come 배열이 만들어지지 않는 에러는 더이상 나오지 않게 되었다..... 하하하하하
여기서 시간을 이렇게 쓸줄이야.
하나 느낀점은,
이렇게 2차원배열에 하나같이 다 때려 넣는건 별로란것.
만약에 2차원 배열에 넣고 돌려야 한다면, 때려넣은다음 돌리고 다시 요소값을 배열에 갱신해 주는건 괜찮은 것 같다.
하지만 회전과 2차원 배열의 이동없이 그냥 요소값이 움직이는 경우라면 굳이 하나의 2차원 배열에 때려 넣지 말자.
그래서 결국, 편의점과 베이스캠프 위치도 bfs로 구하고, 사람들이 움직이는 다음칸도 bfs로 구하고 ,
나머지는 편의점에 도착했을때 사람이 도착했고, 지나가지 못하게 처리.
그리고 움직일수있는 위치가 두가지 이상이라면, 행,열 기준으로 움직이게 했는데
코드트리 해설은 for i // for j 행,열 탐색으로 해서 자동으로 행,열 기준으로 움직일 위치를 잡는다고 나와있다.
코드트리 해설은, 편의점으로부터 bfs를 돌린다음,
step 거리가 가장 짧게 + grid가 베이스 캠프 , 방문한곳(편의점에서 갈수있다.)
이런 복수의 경우를 비교할때
나같은경우는
step 짧은 놈들 배열에 넣고
같은 놈이면 배열값 비교해서 또 새로운 배열에 넣고
그 새로운 배열을 정렬하고.. 또 하고 또하고..
이러지 말고 수학적 사고를 사용해서 min,max,max,min = min(a,b),max(c,d) ... 뭐 이런식으로 해도 훨씬 깔끔하게 할 수있다.
솔직히 코테 풀때 생각은 99% 안날꺼같지만 ㅋㅋ.. 저렇게 하는게 파이썬의 장점이니 유의해보자.
그래서 결국 step ( 거리) , 방문 ( 방문체크) 등을 비교해서 가장 가까운 베이스 캠프를 찾고
** 아마 나는 작년에 length = max(abs(x1-x2),abs(y1-y2)) 이런걸 써가지고 거기까지 가는 거리 최소값.. 구하려고했는데
위와같이 돌아가는 경우면 이동할 수없으니 개같이 탈락이다 ㅋㅋ
마지막으로 코드를 올리고 마무리 하겠다.
여기는 지저분하게 주석 다있는 코드를 올리고, 코드트리에는 깔끔히 정리한 코드를 올릴꺼다 ㅋㅋ
|
from collections import deque
n,m = map(int,input().split())
deb = 1
#0 빈공간 1 베이스캠프, 두명이상 사람 위치가능
maps = [ [ [] for _ in range(n)] for _ in range(n)]
camp = []
base_num = 1
for i in range(n) :
inputs = list(map(int,input().split()))
for items in range(len(inputs)) :
base = inputs[items]
if base == 1 :
maps[i][items].append(base_num)
camp.append((i,items))
base_num += 1
else :
maps[i][items].append(0)
mans = []
combini = []
out = [False]*m #이미 나간애 체크하는 배열
for x in range(m) : #편의점 위치
i_x,i_y = map(int,input().split())
i_x -= 1
i_y -= 1
combini.append((i_x,i_y))
maps[i_x][i_y][0] = x+901 # 편의점 순서대로 입력하기.
mans.append((-1,-1))
def debug() :
print('maps')
for item in maps:
print(*item)
print('combini')
for sx in combini:
print(*sx)
print('camp')
for sx1 in camp:
print(*sx1)
print('people')
for sx2 in mans:
print(*sx2)
print()
#상 좌 우 하
dxs=[-1,0,0,1]
dys=[0,-1,1,0]
#최단거리로 움직인다. #칸의수가 최소가 되는거리라..
def in_range(x,y) :
return 0<=x<n and 0<= y <n
def find_base(time) :
com_x,com_y = combini[time-1]
#모든 베이스 캠프와 거리 비교하기
guri_baserang = []
min_leng = 100
x,y = com_x,com_y
visited1 = [ [0 for _ in range(n)] for _ in range(n)]
queue1 = deque()
queue1.append((x,y))
visited1[x][y] = 1
come1 = [ [None for _ in range(n)] for _ in range(n)]
while queue1 :
x,y = queue1.popleft()
for num1 in range(4) :
nx,ny = x+dxs[num1],y+dys[num1]
if in_range(nx,ny) and visited1[nx][ny] == 0 :
if ( 0 <= maps[nx][ny][0] < 1032) :
queue1.append((nx,ny))
visited1[nx][ny] = visited1[x][y] + 1
come1[nx][ny] = (x,y)
if deb:
for ax in come1:
print(*ax)
for aax in visited1:
print(*aax)
for i in range(len(camp)) :
bx,by = camp[i]
if bx < 0 or by <0 : continue
length = visited1[bx][by]
if length == 0 : continue
guri_baserang.append((length,bx,by))
#print('여기야',guri_baserang)
guri_baserang.sort(key=lambda x:(x[0],x[1],x[2]))
_,final_x,final_y=guri_baserang[0]
return (final_x,final_y)
def is_finish() :
cnt = 0
for xx in range(m) :
tx,ty = mans[xx]
cx,cy = combini[xx]
if tx == cx and ty == cy :
cnt += 1
return cnt != m
def base_camp(time) : #현재 시간 출발하게 한다.
t = time
#먼저 t번사람이 가고싶은 편의점과 가장 가까이있는 베이스 캠프로 이동한다.
if t <= m :
lo_x,lo_y = find_base(t)
mans[t-1] = (lo_x,lo_y)
maps[lo_x][lo_y][0] += 10000 # 못쓰는 베이스캠프로 전향
idx = camp.index((lo_x,lo_y))
camp[idx] = (-1000,-1000) # 베이스 캠프 거리 계산못하게 보내버리기
maps[lo_x][lo_y].append(1000+t) # 사람 넣어버리기
return
def move() :
for ts in range(m) :
qx,qy = mans[ts]
if qx == -1 and qy == -1 : continue # 아직 나오지못했으면 넘겨버리기
if out[ts] == True : continue # 편의점에 있으면 패스
cmx,cmy = combini[ts]
visited = [ [0]*n for _ in range(n)]
queue = deque()
queue.append((qx,qy))
come = [ [None for _ in range(n)] for _ in range(n)]
visited[qx][qy] = 1
while queue :
x,y=queue.popleft()
for num in range(4) :
nx,ny = x+dxs[num], y+dys[num]
#next_lengths = abs(cmx-nx)+abs(cmy-ny)
#print('nx,ny',nx,ny,'가',in_range(nx,ny) and visited[nx][ny] == 0)
if in_range(nx,ny) and visited[nx][ny] == 0 :
#print('nx,ny',nx,ny,'가',0 <= maps[nx][ny][0] < 1000)
#print(maps[nx][ny])
if ( 0 <= maps[nx][ny][0] < 1032) :
#print(x,y,nx,ny)
visited[nx][ny] = visited[x][y]+1
queue.append((nx,ny))
come[nx][ny]=(x,y)
x = cmx
y = cmy
#print(ts,'번째',qx,qy,out[ts],'나갓나체크')
while x !=qx or y != qy :
if come[x][y] == (qx,qy) :
next_x,next_y = x,y
break
(x,y)=come[x][y]
if deb:
print(next_x,next_y,'next체크')
idx = maps[qx][qy].index(1000+ts+1)
peo_value = maps[qx][qy].pop(idx) # 빼버리고
if len(maps[qx][qy]) == 0 :
maps[qx][qy].append(0)
if maps[next_x][next_y][0] == 0 :
maps[next_x][next_y][0]=peo_value
else :
maps[next_x][next_y].append(peo_value)
mans[ts] = (next_x,next_y) # 업데이트 하기
"""
for num in range(4) :
nx,ny = qx+dxs[num], qy+dys[num]
next_lengths = abs(cmx-nx)+abs(cmy-ny)
if in_range(nx,ny) :
if ( 0 <= maps[nx][ny][0] < 1000) and next_lengths < lengths :
mini.append((lengths,num)) #거리와 방향
mini.sort(key=lambda x:(x[0],x[1])) # 최소거리 중에 방향이 젤 작은거(상좌우하 순)
if len(mini) > 0 :
next_len,next_num = mini[0]
idx = maps[qx][qy].index(1000+ts+1)
peo_value = maps[qx][qy].pop(idx) # 빼버리고
if len(maps[qx][qy]) == 0 :
maps[qx][qy].append(0)
next_x,next_y = qx+dxs[next_num],qy+dys[next_num]
if maps[next_x][next_y][0] == 0 :
maps[next_x][next_y][0]=peo_value
else :
maps[next_x][next_y].append(peo_value)
mans[ts] = (next_x,next_y) # 업데이트 하기
"""
return
def is_combini() :
for t in range(m) :
bx,by = mans[t]
cx,cy = combini[t]
if bx == cx and by == cy : #만약 편의점에 도달했으면 편의점 굳게하기
maps[cx][cy][0] += 10000
out[t] = True #얘는 나갔다고 해버리기.
miniute = 0
while is_finish() :
miniute += 1
if deb :
print(miniute,'번째')
debug()
#1번 격자 사람들이동
move()
# 편의점에 도착한 사람들 지나갈수없게하기
is_combini()
# 베이스캠프에서 사람들 출발하게 하기.
base_camp(miniute)
if deb :
print('베이스캠프 피고 편의점 도착하면 굳게 이후 ')
debug()
if miniute == 100 :
break
print(miniute)
|