백준 19236번 청소년 상어 (Python 3)

Baekjoon online judge 19236번 파이썬

 

링크

https://www.acmicpc.net/problem/19236

19236번: 청소년 상어

소스코드

import sys
from copy import deepcopy
input = sys.stdin.readline

fish=[[] for _ in range(16)]
# 현재 방향 ,index-1 만약 -1이면 죽은생선,-2면 상어
index=[[0,-1],[-1,-1],[-1,0],[-1,1],[0,1],[1,1],[1,0],[1,-1]]
data=[[0 for _ in range(4)] for _ in range(4)]
for i in range(4):
    temp=list(map(int,input().split()))
    for j in range(4):
        a,b=temp[2*j],temp[2*j+1]
        fish[a-1]=[j,i,b-1]
        data[i][j]=a-1


def fish_move(fish,data):
    for i in range(16):
        x,y,d=fish[i]
        if d==-1:
            continue

        for j in range(8):
            ny=y+index[(d+j)%8][1]
            nx = x + index[(d + j) % 8][0]
            if 0<=nx<4 and 0<=ny<4 and data[ny][nx]!=-2:
                if data[ny][nx]>=0:
                    oi=data[ny][nx]
                    ox, oy, od =fish[oi]
                    fish[oi]=[x,y,od]
                    data[y][x]=oi
                    fish[i] = [nx, ny, (d + j) % 8]
                    data[ny][nx] = i
                    break
                else:
                    data[y][x]=-1
                    fish[i]=[nx,ny,(d+j)%8]
                    data[ny][nx]=i
                    break

def find_promise(x,y,d,data):
    ans=[]
    for i in range(1,4):
        nx = x + index[d][0]*i
        ny=y+index[d][1]*i
        if 0<=nx<4 and 0<=ny<4 and data[ny][nx]>=0:
            ans.append([nx,ny])
    return ans

now_max=-1
def shark_move(nx,ny,score,fish,data):
    global now_max
    copy_data=deepcopy(data)
    copy_fish=fish[:]
    fish_num=copy_data[ny][nx]
    x,y,d=copy_fish[fish_num]
    score+=(fish_num+1)
    now_max=max(now_max,score)
    copy_fish[fish_num]=[x,y,-1]
    copy_data[ny][nx]=-2

    fish_move(copy_fish,copy_data)

    promise=find_promise(nx,ny,d,copy_data)
    if len(promise)==0:
        return
    for nnx,nny in promise:
        copy_data[ny][nx]=-1
        shark_move(nnx,nny,score,copy_fish,copy_data)

shark_move(0,0,0,fish,data)

print(now_max)