99클럽 코테 스터디 35일차 TIL: 백트래킹 브루트포스

오늘의 문제 | 17825. 주사위 윷놀이

약간 브루트포스, 백트래킹이라는 알고리즘을 보고 당황했다. 이게 정말 그냥 돌린다고 해결할 수 있는 문제인가 싶었다. 마지막이라 약간 문제를 칼을 갈고 찾아왔다는 생각이 드는 난이도이다. 골드2 문제는 푼 기억이 없는데…

우선 백트래킹을 알아보자.

정확히 백트래킹이 어떤 걸 뜻하는지 모르고 문제들을 풀어왔었다. 한번 개념만이라도 간단히 짚어보려 한다.

백트래킹도 결국 브루트포스처럼 모든 경우를 탐색하는 것이긴 하다. 다만 조건이 위배된다고 생각이 들면 전 단계로 다시 돌아가서 탐색하는 느낌이다. 즉 완전히 전부다 탐색하는건 아니지만 완전 탐색 과정 중에 약간의 뒷걸음질을 추가한 느낌으로 보인다.

 

pruning이라는 가지치기 과정으로, 탐색 중 이상한 애들이 생기면 잘라내는 것이다. 아마 윳놀이다보니 비슷하게 계산하면 될 듯하다.

아이디어: 말은 4개가 있고 주사위는 총 10번을 던진다.

여기서 말이 4개 있는 이유는 마지막 예제를 통해 알 수 있다. 모든 주사위가 5일 때, 최대로 나갈 수 있는 말의 개수가 정해져있기에 말이 4개인 것이다. (즉 말이 나갈 수 없는, 불가능한 상황을 연출하지 않기 위해 존재)

 

근데 도저히… 마땅한 방법이 떠오르지를 않는다. 너무 케이스 개수가 많아지는데… 우선 무지성으로 코드를 짜보기로 했다. 하지만 윷놀이 판이 선형적이지 않아서 어쩔 수 없이 연결 리스트를 활용하기로 했다. 다만 또 문제가 되는 것은 30이 2개 있다는 것이다. 어쩔수 없이 힌트라도 찾아보기로 했다.

아이디어: 윷놀이 판을 딕셔너리로 구현하는 것이 제일 쉽다.

우선 배열로 윷놀이 판을 구현하게 되면 굉장히 눈물난다는 것을 확인했다. 따라서 딕셔너리를 통해 각 인덱스에서 이동할 수 있는 인덱스와, 각 인덱스가 가지는 점수를 표현하기로 했다. 약간 놓친 포인트가 있다면 이동하는 주사위의 값들은 모두 순서대로 주어진 것이다. 따라서 어떤 말을 이동할지를 기준으로 생각하면 되는 것이다.

l=[*map(int,input().split())]
answer=0

dict_index={
    0:[1,2,3,4,5],
    1:[2,3,4,5,6],
    2:[3,4,5,6,7],
    3:[4,5,6,7,8],
    4:[5,6,7,8,9],
    5:[21,22,23,24,25],
    6:[7,8,9,10,11],
    7:[8,9,10,11,12],
    8:[9,10,11,12,13],
    9:[10,11,12,13,14],
    10:[27,28,24,25,26],
    11:[12,13,14,15,16],
    12:[13,14,15,16,17],
    13:[14,15,16,17,18],
    14:[15,16,17,18,19],
    15:[29,30,31,24,25],
    16:[17,18,19,20,-1],
    17:[18,19,20,-1,-1],
    18:[19,20,-1,-1,-1],
    19:[20,-1,-1,-1,-1],
    20:[-1,-1,-1,-1,-1],
    21:[22,23,24,25,26],
    22:[23,24,25,26,20],
    23:[24,25,26,20,-1],
    24:[25,26,20,-1,-1],
    25:[26,20,-1,-1,-1],
    26:[20,-1,-1,-1,-1],
    27:[28,24,25,26,20],
    28:[24,25,26,20,-1],
    29:[30,31,24,25,26],
    30:[31,24,25,26,20],
    31:[24,25,26,20,-1]
}
# 각 윷놀이 칸들의 인덱스를 미리 지정하여, 이동할 수 있는 방법을 미리 지정해놓음.

dict_dice={
    -1:0, 0:0, 1:2, 2:4, 3:6, 4:8, 5:10, 6:12, 7:14, 8:16, 9:18, 10:20,
    11:22, 12:24, 13:26, 14:28, 15:30, 16:32, 17:34, 18:36, 19:38, 20:40, 21:13, 22:16,
    23:19, 24:25, 25:30, 26:35, 27:22, 28:24, 29:28, 30:27, 31:26
}
# 각 윷놀이 인덱스에 해당하는 점수

def backtracking(depth, score, horses):
    global answer
    if depth==10:
        answer=max(answer,score)
        return
    for i in range(4): # 각 말들이 이동하는 모든 케이스를 체크함. i는 어떤 말 고를지 고름.
        x=horses[i] # 몇 번 째 말을 이동할 것인가, 그리고 그 말의 위치
        if x==-1: continue
        x=dict_index[x][l[depth]-1]
        # 본인이 이동할 수 있는 칸으로 갱신함.

        if x==-1 or (x not in horses):
            # 해당 케이스가 옳은지 확인하기 위해 값을 갱신했다가 해지함.
            temp=horses[i]
            horses[i]=x # 과연 이 케이스일 때는 최대가 될까?
            backtracking(depth+1, score+dict_dice[x], horses)
            horses[i]=temp # 다시 원상 복귀
        
backtracking(0, 0, [0,0,0,0])
print(answer)

자세한 코드 설명은 주석으로 작성했으니 생략하겠다. 확실히 백트래킹을 풀면서 어떤 아이디어를 위주로 생각해야하는지가 감이 잡혔다. 케이스를 테스트해보기 위해 특정 값으로 세팅해두었다가 다시 원상 복구시키는 과정을 통해 모든 케이스를 돌아본다는 느낌을 받았다.

비록 많은 코드를 참조했음에도 백트래킹을 어떻게 활용해야할지가 감이 잡혔다는 점에서 만족스럽다.

오늘의 회고

35일 간의 여정에서의 마무리 문제를 검색해서 풀었다는 게 매우 아쉽긴하지만, 마지막이 가장 큰 도움이 되었던 듯하다. 어려운 문제였기에 오히려 날 자극해서 문제를 풀게 한게 아닌가 싶었다. 회고록은 나중에 따로 작성할 테니 오늘의 회고는 짧게 적지만, 백트래킹이라는 분야에 약간 눈을 뜨게 해줬다는게 맘에 든다.