青少年サメ派
3364 ワード
質問する
input
1行目から4行目まで、各欄の魚の情報は1行目から順に与えられます.魚の情報は2つの整数ai,biからなり,aiは魚の番号を表し,biは方向を表す.方向biは8以下の自然数を表し,1から順に↑,↖,←,͜,↓,‐,‐,→,,,,,∧である.
output
サメが食べられる魚番号の最高値を出力します.
TODO
BFS
물고기 위치
상어 0,0에 놓기
물고기 움직이기
상어 움직이기
움직이는 방향 전부 포함하기
CODE
input_data = [list(map(int,input().split())) for _ in range(4)]
fish_dic = {}
space = [[0 for _ in range(4)] for _ in range(4)]
for i in range(4) :
for j in range(0,8,2) :
space[i][j//2] = input_data[i][j]
fish_dic[input_data[i][j]] = [i,j//2,input_data[i][j+1] - 1]
# 1부터 순서대로 ↑, ↖, ←, ↙, ↓, ↘, →, ↗
direction = [(-1,0),(-1,-1), (0,-1), (1,-1),(1,0),(1,1),(0,1),(-1,1)]
from collections import deque
def copy_dic(ori):
ret = {}
for key in ori.keys():
ret[key] = ori[key][:]
return ret
def copy_space(ori):
temp = [[0 for _ in range(4)] for _ in range(4)]
for i in range(4):
for j in range(4):
temp[i][j] = ori[i][j]
return temp
def fish_move(ts1,tfk1):
ts = copy_space(ts1)
tfk = copy_dic(tfk1)
for key in range(1,17):
if tfk.get(key):
x,y,d = tfk[key]
nx,ny = x+direction[d][0], y+direction[d][1]
succ = False
for _ in range(8):
if 0<=nx<4 and 0<=ny<4 and ts[nx][ny] != -1 :
succ = True
break
d+=1
nx,ny = x+direction[d%8][0], y+direction[d%8][1]
if succ:
if tfk.get(ts[nx][ny]):
tfk[ts[nx][ny]][0], tfk[ts[nx][ny]][1] = x,y
tfk[key][0], tfk[key][1], tfk[key][2] = nx,ny,d%8
ts[x][y],ts[nx][ny] = ts[nx][ny],ts[x][y]
return ts,tfk
# space, fish_dic = fish_move(space,fish_dic) # first move
def shark_move(shark_position,space):
x,y,d = shark_position
ret = 0
if (x,y) == (0,0):
del fish_dic[space[0][0]]
ret += space[0][0]
space[0][0] = -1
temp_space,temp_fish_dic = fish_move(space,fish_dic)
q = deque([(x,y,d,temp_space,ret,temp_fish_dic)])
while q :
x,y,d,temp_space,point, temp_fish_dic= q.popleft()
if ret<point :
ret= point
temp_space[x][y] = 0 # 이동
px,py = direction[d]
nx,ny = x,y
while 0<=nx + px<4 and 0<=ny+py<4 :
nx,ny = nx+px,ny+py
if 0<=nx<4 and 0<=ny<4 and temp_space[nx][ny] != 0 :
key = temp_space[nx][ny]
fx,fy,fd = temp_fish_dic[key]
nd=fd
del temp_fish_dic[key]
temp_space[nx][ny] = -1
ts,tfk = fish_move(temp_space,temp_fish_dic)
q.append((nx,ny,nd,ts,point+key, tfk))
temp_space[nx][ny] = key
temp_fish_dic[key] = [fx,fy,fd]
return ret
shark_position = [0,0,fish_dic[space[0][0]][2]]
print(shark_move(shark_position,space))
振り返る
説明があまりにも詳しくて、答えが間違っていないので、第1セットで答えられます.
コードが乱れているので、もう一度整理してもいいです.
Reference
この問題について(青少年サメ派), 我々は、より多くの情報をここで見つけました https://velog.io/@ifelifelse/청소년-상어-파이썬-백준-19236テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol