파이썬 알고리즘 186번 | [백준 2116번] - 주사위 쌓기 - 브루트포스, DFS

186. 주사위 쌓기

1) 어떤 전략(알고리즘)으로 해결?

• 브루트 포스, dfs

2) 코딩 설명

• 주사위 여섯개 면이 밑면으로 왔을 때 각각 경우를 확인하면 된다.

<내 풀이>

import sys
sys.setrecursionlimit(10**6)
n = int(sys.stdin.readline().rstrip())
dice =[]
maxi =-99999
for i in range(n) :
    dice.append(list(map(int,sys.stdin.readline().rstrip().split())))
faces=[]

def dfs(diceNum, face, res , faces) :
    global maxi

    if diceNum == n :

        if maxi < res :
            maxi = res
        return

    else : 
        faces.append(face)
        myFace = dice[diceNum].index(dice[diceNum-1][face])

        if myFace == 0 or  myFace == 5 :
            res+=(max(dice[diceNum][1:5]))
                    
            if myFace == 0:
                nextFace = 5
            else : nextFace =0

        elif myFace ==1 or myFace ==3 :
            res+=max([dice[diceNum][0],dice[diceNum][2],dice[diceNum][4], dice[diceNum][5]])

            if myFace == 1:
                nextFace = 3
            else : nextFace = 1

        else : # 2, 4
            res+=max([dice[diceNum][0],dice[diceNum][1],dice[diceNum][3], dice[diceNum][5]])

            if myFace == 2:
                nextFace = 4
            else : nextFace =2

        dfs(diceNum+1, nextFace, res, faces)
        
for i in range(6) :
    res= 0
    faces=[]
    dfs(0, i, res, faces)

print(maxi)

<내 틀렸던 풀이, 문제점>

recursion error

import sys

n = int(sys.stdin.readline().rstrip())
dice =[]
total =[]
for i in range(n) :
    dice.append(list(map(int,sys.stdin.readline().split())))

def dfs(diceNum, face, dice_face) :
    if diceNum == n :
        res = 0
        for i in dice_face :
            res+=max(i)
        total.append(res)
        return
    
    elif diceNum == 0 :
        tmp_dice_face = dice_face.copy()
        if face == 0 or  face == 5 :
            dice_face.append(dice[diceNum][1:5])
            if face == 0:
                nextFace = 5
            else : nextFace =0
            

        elif face ==1 or face ==3 :
            lis =[dice[diceNum][0],dice[diceNum][2],dice[diceNum][4], dice[diceNum][5]]
            dice_face.append(lis)
            if face == 1:
                nextFace = 3
            else : nextFace = 1
            

        else : # 2, 4
            lis =[dice[diceNum][0],dice[diceNum][1],dice[diceNum][3], dice[diceNum][5]]
            dice_face.append(lis)
            if face == 2:
                nextFace = 4
            else : nextFace = 2
        
        dfs(diceNum+1, nextFace, dice_face)
        dice_face = tmp_dice_face

    else : 
        tmp_dice_face = dice_face.copy()
        myFace = dice[diceNum].index(dice[diceNum-1][face])

        if myFace == 0 or  myFace == 5 :
            dice_face.append(dice[diceNum][1:5])
                    
            if face == 0:
                nextFace = 5
            else : nextFace =0

        elif myFace ==1 or myFace ==3 :
            lis =[dice[diceNum][0],dice[diceNum][2],dice[diceNum][4], dice[diceNum][5]]
            dice_face.append(lis)
            if face == 1:
                nextFace = 3
            else : nextFace = 1

        else : # 2, 4
            lis =[dice[diceNum][0],dice[diceNum][1],dice[diceNum][3], dice[diceNum][5]]
            dice_face.append(lis)

            if face == 2:
                nextFace = 4
            else : nextFace =2

        dfs(diceNum+1, nextFace, dice_face)
        dice_face = tmp_dice_face

for i in range(6) :
    dice_face = [] # 옆면 저장 소 
    dfs(0, i, dice_face)

print(max(total))

• 9프로에서 recursion 에러~

메모리 초과

모든 입력을 배열에 저장하면 당연히 메모리 초과

import sys
sys.setrecursionlimit(10**6)
n = int(sys.stdin.readline().rstrip())
dice =[]
maxi =-99999
for i in range(n) :
    dice.append(list(map(int,sys.stdin.readline().rstrip().split())))

def dfs(diceNum, face, dice_face) :
    global maxi
    if diceNum == n :
        res = 0
        for i in dice_face :
            res+=max(i)
        if maxi < res :
            maxi = res
        return
    
    elif diceNum == 0 :

        if face == 0 or  face == 5 :
            dice_face.append(dice[diceNum][1:5])
            if face == 0:
                nextFace = 5
            else : nextFace = 0
            

        elif face ==1 or face ==3 :
            lis =[dice[diceNum][0],dice[diceNum][2],dice[diceNum][4], dice[diceNum][5]]
            dice_face.append(lis)
            if face == 1:
                nextFace = 3
            else : nextFace = 1
            

        else : # 2, 4
            lis =[dice[diceNum][0],dice[diceNum][1],dice[diceNum][3], dice[diceNum][5]]
            dice_face.append(lis)
            if face == 2:
                nextFace = 4
            else : nextFace = 2
        
        dfs(diceNum+1, nextFace, dice_face)
        #dice_face = tmp_dice_face

    else : 
        myFace = dice[diceNum].index(dice[diceNum-1][face])

        if myFace == 0 or  myFace == 5 :
            dice_face.append(dice[diceNum][1:5])
                    
            if face == 0:
                nextFace = 5
            else : nextFace =0

        elif myFace ==1 or myFace ==3 :
            lis =[dice[diceNum][0],dice[diceNum][2],dice[diceNum][4], dice[diceNum][5]]
            dice_face.append(lis)
            if face == 1:
                nextFace = 3
            else : nextFace = 1

        else : # 2, 4
            lis =[dice[diceNum][0],dice[diceNum][1],dice[diceNum][3], dice[diceNum][5]]
            dice_face.append(lis)

            if face == 2:
                nextFace = 4
            else : nextFace =2

        dfs(diceNum+1, nextFace, dice_face)
        #dice_face = tmp_dice_face

for i in range(6) :
    dice_face = [] # 옆면 저장 소 
    dfs(0, i, dice_face)

print(maxi)

• 메모리 초과 에러~ 화가나네

리스트에 저장하지 말고 RES 를 바로바로 계산해보자

import sys
sys.setrecursionlimit(10**6)
n = int(sys.stdin.readline().rstrip())
dice =[]
maxi =-99999
for i in range(n) :
    dice.append(list(map(int,sys.stdin.readline().rstrip().split())))

def dfs(diceNum, face, res) :
    global maxi
    if diceNum == n :
        print(maxi, res)
        if maxi < res :
            
            maxi = res
        
        return
    
    elif diceNum == 0 :
        if face == 0 or  face == 5 :
            res+=(max(dice[diceNum][1:5]))
            if face == 0:
                nextFace = 5
            else : nextFace = 0
            

        elif face ==1 or face ==3 :
            res+=max([dice[diceNum][0],dice[diceNum][2],dice[diceNum][4], dice[diceNum][5]])

            if face == 1:
                nextFace = 3
            else : nextFace = 1
            

        else : # 2, 4
            res+=max([dice[diceNum][0],dice[diceNum][1],dice[diceNum][3], dice[diceNum][5]])

            if face == 2:
                nextFace = 4
            else : nextFace = 2
        
        dfs(diceNum+1, nextFace, res)
        #dice_face = tmp_dice_face

    else : 
        myFace = dice[diceNum].index(dice[diceNum-1][face])

        if myFace == 0 or  myFace == 5 :
            res+=(max(dice[diceNum][1:5]))
                    
            if face == 0:
                nextFace = 5
            else : nextFace =0

        elif myFace ==1 or myFace ==3 :
            res+=max([dice[diceNum][0],dice[diceNum][2],dice[diceNum][4], dice[diceNum][5]])

            if face == 1:
                nextFace = 3
            else : nextFace = 1

        else : # 2, 4
            res+=max([dice[diceNum][0],dice[diceNum][1],dice[diceNum][3], dice[diceNum][5]])

            if face == 2:
                nextFace = 4
            else : nextFace =2

        dfs(diceNum+1, nextFace, res)
        #dice_face = tmp_dice_face

for i in range(6) :
    res= 0
    dfs(0, i, res)

print(maxi)

• 이건 그냥 틀렸다구 뜸, 왜냐하면 face, myface를 바꿔썼기 때문이지 ^^

<반성 점>

• 기존에 나는 배운 모든 것을 리스트에 넣고 비교하는 과정을 거쳤었는데 그러면 메모리초과가 난다구 한다. 최대한 메모리를 아끼며 ~ 코드를 짜보자

<배운 점>