아직 계정이 없으신가요? 회원가입

Dev. Talk

Garage game 로직 문의..

회원사진dltjdtn321
348 views2021-10-19 17:18

아래처럼 단순 제거 후 내려가는 로직밖에 안 떠오르는데

블록의 색상이 모두 다른 경우에, N=8부터 시간 초과가 나네요


더 최적화할 부분이나

간단히라도 로직 힌트 부탁드립니다..!



import sys

def beatify(txt,ti):
    print(txt,ti)
    for y in range(len(arr[ti])-1,-1,-1):
        print(arr[ti][y])

def cpy(ti,r_arr):
    arr[ti]=[[0 for c in range(N)] for r in range((4-ti)*N)]
    # arr[ti]=[[0 for c in range(N)] for r in range(3*N)]
    visited[ti]=[[False for c in range(N)] for r in range(N)]
    for x in range(N):
        yc=0
        for y in range((4-ti)*N):
            if arr[ti-1][y][x]==0:
                break
            if not [y,x] in r_arr:
                arr[ti][yc][x]=arr[ti-1][y][x]
                yc+=1

def clk(y,x,ti,score):
    xyXY=[x,y,x,y]
    qu=[[y,x]]
    visited[ti-1][y][x]=True
    score+=1
    r_arr=[[y,x]]
    while qu:
        cy,cx=qu.pop()
        for di in [[-1,0],[0,1],[1,0],[0,-1]]:
            ny=cy+di[0]
            nx=cx+di[1]
            if ny<0 or nx<0 or ny>=N or nx>=N:
                continue
            if visited[ti-1][ny][nx] or arr[ti-1][ny][nx]!=arr[ti-1][y][x]:
                continue
            qu.append([ny,nx])
            visited[ti-1][ny][nx]=True
            score+=1
            r_arr.append([ny,nx])
            if nx<xyXY[0]:
                xyXY[0]=nx
            if ny<xyXY[1]:
                xyXY[1]=ny
            if nx>xyXY[2]:
                xyXY[2]=nx
            if ny>xyXY[3]:
                xyXY[3]=ny
    return [score,xyXY,r_arr]

def dfs(score,ti):
    global ans
    for y in range(N):
        for x in range(N):
            if arr[ti-1][y][x]==0 or visited[ti-1][y][x]:
                continue
            score2,xyXY,r_arr=clk(y,x,ti,score)
            score2+=(xyXY[2]-xyXY[0]+1)*(xyXY[3]-xyXY[1]+1)
            if ans<score2:
                ans=score2
            if ti==3:
                # cpy(ti,r_arr)
                # beatify("fin/"+str(score2),ti)
                continue
            cpy(ti,r_arr)
            # beatify("cpy",ti)
            dfs(score2,ti+1)

N=int(sys.stdin.readline())
arr=[[] for v in range(4)]
chd={}
for i in range(3*N):
    tmp=list(map(int,sys.stdin.readline().split()))
    # tmp=[]
    for j in range(N):
        # tmp.append(i*N+j)
        if tmp[j] in chd.keys():
            chd[tmp[j]]+=1
        else:
            chd[tmp[j]]=1
    arr[0].insert(0,tmp)

ans=0
visited=[[[False for c in range(N)] for r in range(N)] for t in range(4)]
dfs(0,1)

print(ans)