코드트리 | 코딩테스트 준비를 위한 알고리즘 정석
국가대표가 만든 코딩 공부의 가이드북 코딩 왕초보부터 꿈의 직장 코테 합격까지, 국가대표가 엄선한 커리큘럼으로 준비해보세요.
www.codetree.ai
저번에 풀었던 문제지만 한번 복습겸 두번 풀어봤다.
2회차풀이
|
import sys
import copy
import faulthandler
faulthandler.enable()
#print(sys.version)
sys.stdin = open("input_magerunner_1.txt",'r')
deb =0
n,m,k = map(int,input().split())
#맵은 2차원, 출구도 2차원
# 러너는 여러명가능하니 3차원, 회전때문에 사용.
maps = [ list(map(int,input().split())) for _ in range(n)]
runner = [ [ [None] for _ in range(n)] for _ in range(n)]
exit = [ [False]*n for _ in range(n)]
arr_runner = []
dxs=[-1,1,0,0]
dys=[0,0,-1,1]
for mans in range(m) :
r1,c1 = map(int,input().split())
r1-=1
c1-=1
arr_runner.append((r1,c1))
runner[r1][c1].append(mans)
#인덱스 0 부터 각 러너의 정보가 담긴다.
#인덱스가 곧 그 러너의 등번호
exit_x,exit_y = map(int,input().split())
exit_x-=1
exit_y-=1
exit[exit_x][exit_y] = True
def in_range(x,y) :
return 0<=x<n and 0<=y<n
def one_runner_move(x,y) :
if deb:
print('one_runner_move')
walk = 0
min_length = abs(exit_x-x) + abs(exit_y-y)
for i in range(4) :
nx,ny = x+dxs[i],y+dys[i]
nx_length = abs(exit_x-nx) + abs(exit_y-ny)
if in_range(nx,ny) and nx_length < min_length and maps[nx][ny] ==0:
x,y = nx,ny
walk = 1
return x,y,walk
#아무것도 안되면 걍 x,y
return x,y,walk
def runner_move() :
global runner
temp_runner = [ [ [] for _ in range(n)] for _ in range(n)]
all_walk_point = 0
#러너 개수만큼 하나하나 이동시키기.
for i in range(m) :
tx,ty = arr_runner[i]
if tx== -1 or ty == -1 : continue
ntx,nty,walk_point = one_runner_move(tx,ty)
all_walk_point += walk_point
if exit[ntx][nty] : # 만약 이동한 다음이 출구라면, 퇴장처리
arr_runner[i] = (-1,-1)
else :
assert isinstance(temp_runner[ntx][nty],list)
temp_runner[ntx][nty].append(i)
#여기서 메모리 많이쓸꺼같은느낌
for i in range(n) :
for j in range(n) :
runner[i][j] = temp_runner[i][j]
return all_walk_point
def check(power,runner) :
for i in range(n):
for j in range(n) :
if in_range(i+power,j+power):
run_cnt = 0
exit_cnt = 0
for k in range(power+1):
for x in range(power+1):
if in_range(i+k,j+x):
if exit[i+k][j+x] :
exit_cnt = 1
#print(i,j,k,x,i+k,j+x,power,'체크')
# for 문으로 불러와주니까 에러안남?
#for xk in runner:
# pass
#print(*xk)
#print()
if len(runner[i+k][j+x]) != 0 :
run_cnt =1
#어라 둘다 발견해버렸다면.?
#그위치와 파워를 리턴해야한다.
if run_cnt == 1 and exit_cnt == 1 :
return (i,j,power)
return (-1,-1,0)
def make_sagak() :
global runner
#0,0부터 크기 2 정사각형으로 다돌리고
#0,0부터 크기 3 정사각형으로 다돌리고.. 해서 1명이라도 포함되면 바로 리턴.
power = 1
possible = True
while possible :
(i,j,mid) = check(power,runner)
if i == -1 :
power +=1
else :
possible=False
return (i,j,mid+1)
def select_rotate_map(x,y,mid,check) :
global maps
#check 는 maps일때
# check 가 True 면 맵 배열이라 깎아줘야한다.
temp_arr2 =[ [0]*n for _ in range(n)]
for i in range(n):
for j in range(n) :
temp_arr2[i][j] = maps[i][j]
for i in range(mid):
for j in range(mid) :
if check :
tems = maps[i+x][j+y] -1
if tems <0 :
tems = 0
temp_arr2[j+x][mid-1-i+y] = tems
else :
tems = maps[i+x][j+y]
temp_arr2[j+x][mid-1-i+y] = tems
maps = temp_arr2.copy()
return
def select_rotate_runner(x,y,mid,check,runner) :
if deb:
print('select_rotate_runne')
assert len(runner) != 0
assert len(runner[0]) != 0
assert isinstance(runner[0][0], list)
#check 는 maps일때
# check 가 True 면 맵 배열이라 깎아줘야한다.
temp_arr =[ [ [] for _ in range(n)] for _ in range(n)]
for i in range(n):
for j in range(n) :
for k in range(len(runner[i][j])):
temp_arr[i][j].append(runner[i][j][k])
#print('check')
for i in range(mid):
for j in range(mid) :
runner[j+x][mid-1-i+y] = temp_arr[i+x][j+y]
return
def select_rotate_exit(x,y,mid,check) :
global exit
temp_arr1 =[ [False]*n for _ in range(n)]
for i in range(n):
for j in range(n) :
if exit[i][j]:
temp_arr1[i][j] = True
for i in range(mid):
for j in range(mid) :
if exit[i+x][j+y]:
temp_arr1[j+x][mid-1-i+y] = True
else :
temp_arr1[j+x][mid-1-i+y] = False
for i in range(n) :
for j in range(n) :
if temp_arr1[i][j]:
exit[i][j] = True
else :
exit[i][j] = False
return
def update_runner() :
for i in range(n) :
for j in range(n) :
if len(runner[i][j]) != 0 :
for k in range(len(runner[i][j])) :
items = runner[i][j][k]
arr_runner[items] = (i,j)
return
def update_exit() :
global exit_x,exit_y
for i in range(n):
for j in range(n) :
if exit[i][j] :
exit_x,exit_y = i,j
return
def rotate_exit():
#나는이걸 .. 그냥 for문으로 작은 크기 다 찾게 해버릴래.
#그리고 회전 미리 구현해두기.
(rx,ry,leng) = make_sagak()
#maps돌리기
select_rotate_map(rx,ry,leng,True)
#runner 돌리기
select_rotate_runner(rx,ry,leng,False,runner)
update_runner()
#exit 돌리기
select_rotate_exit(rx,ry,leng,False)
update_exit()
return
def check_exit_all():
cnt =0
for i in range(n) :
for j in range(n):
if len(runner[i][j]) != 0 :
cnt += 1
if cnt == 0 :
return True
else :
return False
#시뮬레이션
point = 0
for _ in range(k) :
point += runner_move()
if check_exit_all() :
break
rotate_exit()
print(point)
print(exit_x+1,exit_y+1)
|
이거 풀다가 엄청난 오류 및 copy 남발로 고생했던 케이스가 있어 주의해야할 부분을 남겨 놓겠다.
2회차 풀이 하며 주의한점
먼저 탈출구 2차원배열, 미로 2차원배열, 사람위치 3차원배열 이렇게 써먹었다.
이렇게 하다 보니 큰 오류가 발생했는데..
바로
temp = ori_arr < 임시 값 해주고
for i in range(n):
for j in range(n):
temp [i][j+시계방향] = ori_arr[i][j]
ori_arr = temp
위방법을 했다가 어마어마한 에러 segment Error 11 을 만났다.
이건 위에 3차원배열을 저렇게 회전시키면서 적용하다가
파이썬문제인제 코드트리 홈페이지 문제인지 메모리 접근 에러가 발생했고,
굉장히 특이하게 해당 배열을 불러오기전에
for i in runner :
pass
를 하니까 정상적으로 되었다. ( 진짜 원인이 뭘까 바로 선언해서 주소값이 정신을 차려줘서 그런가 ?? )
결국엔 시간도 273ms 정도에 관련에러 디버깅 하느라 시간이 너무오래걸렸다.
위와같은 에러를 피하기 위해선
바보같이 저렇게 따로 먹이지 말고,
temp = ori_arr < 임시 값 해주고
for i in range(n):
for j in range(n):
ori_arr[i][j+시계방향]= temp[i][j]
위와같이 바로 original 배열값에 바로 넣어주자. 위의 temp 값에다가 시계방향 돌리는 처리를 할때
바로 오리지널 배열에 넣으라는말.
이걸해줘야 segment 에러를 피할 수 있고, 어찌됐건 3차원배열을 [i+k][j+x] 와같이 중첩된 for문에서 접근하려고 하면, 모듈러에 따라 안될수도있다고 한다..
그리고 사람 인덱스를 하나하나 저장해야하던탓에 update도 체크 해줘야했다.
그리고 while 문에다가 넣고 박스를 찾으면 possible = False 하게 했는데 이것도 굉장히 안좋았다.
그냥 문제조건에서 최대일때 까지로 for문 돌리는게 훨씬 안정적이니 이걸 꼭 참고해야겠다.
3회차 풀이
|
import sys
import copy
#print(sys.version)
sys.stdin = open("input_magerunner_2.txt",'r')
#n 미로크기 m 참가자수 k 게임시간
n,m,k = map(int,input().split())
maps = [ list(map(int,input().split())) for _ in range(n)]
arr_3rd_people = [ [0]*n for _ in range(n)]
for num in range(m) :
r,c = map(int,input().split())
r-=1
c-=1
arr_3rd_people[r][c] += 1
exit_x,exit_y = map(int,input().split())
exit_x-=1
exit_y-=1
# 출구는 -1
maps[exit_x][exit_y] = -1
def in_range(x,y) :
return 0<=x<n and 0<=y<n
def one_people_move(x,y) :
movement = 0
exit_move = abs(exit_x-x) + abs(exit_y-y)
dxs=[-1,1,0,0]
dys=[0,0,1,-1]
for i in range(4) :
nx,ny = x+dxs[i],y+dys[i]
after_exit_move = abs(exit_x-nx) + abs(exit_y-ny)
if in_range(nx,ny) and (maps[nx][ny] == -1 or maps[nx][ny] ==0) and exit_move > after_exit_move :
movement = arr_3rd_people[x][y]
x,y = nx,ny
return (movement,x,y)
return (movement,x,y)
def people_move() :
point = 0
temp_arr = [ [0]*n for _ in range(n)]
for i in range(n) :
for j in range(n) :
if arr_3rd_people[i][j] >0 :
movement,nx1,ny1=one_people_move(i,j)
point += movement
if maps[nx1][ny1] == -1 :
arr_3rd_people[i][j] = 0
temp_arr[nx1][ny1] += arr_3rd_people[i][j]
for i in range(n) :
for j in range(n) :
arr_3rd_people[i][j] = temp_arr[i][j]
return point
def rotate_select_maps(x,y,mid,arr,is_human) :
temp_arr = [ [0]*n for _ in range(n)]
# 기존배열 값에 템프배열을 넣어야했음.
# 나는 템프 배열에 기존배열값을 넣고 기존배열=템프베열 하다보니 에러가 발생
for i in range(n) :
for j in range(n) :
temp_arr[i][j] = arr[i][j]
for i in range(mid):
for j in range(mid):
if is_human :
if temp_arr[x+i][y+j] > 0 :
temp_arr[x+i][y+j] -= 1
arr[x+j][mid+y-i-1] = temp_arr[x+i][y+j]
return
def find_exit_people() :
for power in range(2,11) :
for i in range(n) :
for j in range(n) :
exit_cnt = 0
people_cnt = 0
if in_range(i+power-1,j+power-1):
for x in range(power) :
for k in range(power):
if arr_3rd_people[i+x][j+k] > 0 :
people_cnt = 1
if maps[i+x][j+k] == -1 :
exit_cnt = 1
if people_cnt == 1 and exit_cnt == 1 :
return (i,j,power)
return (-1,-1,-1)
def exit_and_people_rotate() :
x1,y1,mid = find_exit_people()
rotate_select_maps(x1,y1,mid,maps,True)
rotate_select_maps(x1,y1,mid,arr_3rd_people,False)
return
def update_exit():
global exit_x,exit_y
for i in range(n) :
for j in range(n):
if maps[i][j] == -1 :
exit_x,exit_y = i,j
return
answer = 0
for _ in range(k) :
answer += people_move()
exit_and_people_rotate()
update_exit()
print(answer)
print(exit_x+1,exit_y+1)
|
친구와 같이 풀었는데 그친구가 자료구조에 대한 첨언을 몇가지 해주었다.
1번 - 출구를 그냥 maps 에 넣어서 -1 로 표시하자
2번 - 사람여러명이 들어갈수있는거 3차원배열로 했는데 꼭 사람 인덱스가 중요하냐? 그냥 사람수로 해버리면 되는거 아니냐?
위 두가지 조언을 듣고 코드를 처음부터 다시 짜기 시작했다.
그러니 이전에 발생하던 불필요한 충돌이 없어졌고.. 구조는 동일한데 배열이 3차원이냐 2차원이냐에 따라 모듈처리에 문제가 있나보다.. 최대한 가능하면, 인덱스가 주어지지않았다면 사람숫자로 2차원배열을 컨트롤 하는게 바람직해보인다.
그리고 copy,deepcopy 보단 웬만하면 그냥 for 문쓰는게 더 안정적이라고 말했다.(마이크로소프트 친구 왈 )
그리고 하나 재밋는걸 찾앗는데 이건 바로 포스트 이어쓰겠다.