[BOJ][🟡2][백준#17825] 주사위 윷놀이

문제 출처

BAEKJOON Online Judge #17825

문제

주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다.

처음에는 시작 칸에 말 4개가 있다. 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 파란색 화살표를 타야 하고, 이동하는 도중이거나 파란색이 아닌 칸에서 이동을 시작하면 빨간색 화살표를 타야 한다. 말이 도착 칸으로 이동하면 주사위에 나온 수와 관계 없이 이동을 마친다. 게임은 10개의 턴으로 이루어진다. 매 턴마다 1부터 5까지 한 면에 하나씩 적혀있는 5면체 주사위를 굴리고, 도착 칸에 있지 않은 말을 하나 골라 주사위에 나온 수만큼 이동시킨다. 말이 이동을 마치는 칸에 다른 말이 있으면 그 말은 고를 수 없다. 단, 이동을 마치는 칸이 도착 칸이면 고를 수 있다. 말이 이동을 마칠 때마다 칸에 적혀있는 수가 점수에 추가된다.

주사위에서 나올 수 10개를 미리 알고 있을 때, 얻을 수 있는 점수의 최댓값을 구해보자.

입력

첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다.

출력

얻을 수 있는 점수의 최댓값을 출력한다.

예제

예제 1

입력

1 2 3 4 1 2 3 4 1 2

출력

190

예제 2

입력

1 1 1 1 1 1 1 1 1 1

출력

133

예제 3

입력

5 1 2 3 4 5 5 3 2 4

출력

214

예제 4

입력

5 5 5 5 5 5 5 5 5 5

출력

130

My Sol

def main():
    def make_vals():
        vals = [0]*32
        for i in range(21):
            vals[i] = 2*i
        vals[21], vals[22], vals[23] = 13, 16, 19
        vals[24], vals[25] = 22, 24
        vals[26], vals[27], vals[28] = 28, 27, 26
        vals[29], vals[30], vals[31] = 25, 30, 35
        return vals

    def make_children():
        children = {}
        for n in range(20):
            children[n] = n+1
        for a, b in ((21, 23), (24, 25), (26, 28), (29, 31)):
            for n in range(a, b):
                children[n] = n+1
        children[23] = children[25] = children[28] = 29
        children[31] = 20
        children[20] = -1

        special_children = {5: 21, 10: 24, 15: 26}
        return children, special_children

    def move(move_cnt, acc, pos_list, pos_set):
        def move_next(is_special, cur_max_acc):
            ret = cur_max_acc
            step_cnt = 1
            cur_pos = special_children[p] if is_special else children[p]
            if cur_pos != -1:
                while step_cnt < cur_move:
                    cur_pos = children[cur_pos]
                    if cur_pos==-1: break
                    step_cnt += 1

            new_pos_list = pos_list[:]
            new_pos_list[pi] = cur_pos
            new_pos_set = pos_set - {p}
            if cur_pos==-1:
                new_pos_list.pop(pi)
                ret = max(ret, move(move_cnt+1, acc, new_pos_list, new_pos_set))
            else:
                if cur_pos in pos_set: return 0
                ret = max(ret, move(move_cnt+1, acc+vals[cur_pos], new_pos_list, new_pos_set|{cur_pos}))
            return ret

        if move_cnt==10: return acc

        cur_max_acc = acc
        cur_move = moves[move_cnt]
        for pi in range(len(pos_list)):
            p = pos_list[pi]
            is_special = p in special_children_set
            cur_max_acc = max(cur_max_acc, move_next(is_special, cur_max_acc))
        return cur_max_acc


    moves = list(map(int, input().split()))
    vals = make_vals()
    children, special_children = make_children()
    special_children_set = {5, 10, 15}
    return move(0, 0, [0, 0, 0, 0], {0})

print(main())

어떤 알고리즘을 써야하나 감이 안 왔는데 사실상 쌩노가다 구현 문제인 것 같다. DFS를 활용해 문제를 해결했다.

1. 윷놀이판과 규칙을 트리 방식을 사용해 자식을 바라보도록 했다. 값 자체를 번호로 하기에는 서로 다른 경로에 같은 값이 있는 경우도 있어서 각 노드의 번호를 붙여주고 해당 노드의 번호가 가지는 값을 따로 지정해주었다. 이를 각각 make_children과 make_vals 함수를 통해 분리해서 구현했다.
2. DFS 함수 move를 시작한다. parameter로는 이동 횟수를 의미하는 move_cnt, 누적값인 acc, 말들의 위치 정보 리스트 pos_list, 위치 정보 set pos_set이다.
3. 현재 이동할 수 있는 스텝 수를 cur_move로 두었다. 이는 현재 이동 횟수 move_cnt를 이동스텝 배열 moves의 인덱스로 하여 구한다.
4. 각 말들의 정보인 pos_list의 각 말들을 움직인다고 가정한다. 만약 파란색 위치에 있어서 더 빠르게 이동할 수 있는 경우라면 special하다고 한다. 이미 find_children 함수에서 special한 경우의 위치와 children 정보를 구해두었다.
5. 현재 말의 위치가 special한 위치에 있는지, 아닌지에 따라서 이동 children이 달라지므로 이를 확인한다. move_next 함수에서 다음을 진행한다.
6. move_next 함수는 이동 스텝 횟수만큼 경로를 따라 이동하여 도착 지점을 계산한다. 이것이 값이 40인 20번 노드를 넘는다면 도착 지점에 도착한 것이다. 도착지점의 번호를 -1로 설정했다.
7. 모든 이동을 마치고 현재 위치가 -1이라면 이동할 수 없는 말이 되기 때문에 new_pos_list에서 빼준다.
8. 만약 도착점이 -1이 아니라면, 이미 그곳에 말이 있는지 여부를 확인한다. 이것은 pos_set을 통해 알 수 있다. 만약 있다면 무의미한 이동이므로 현재 ret을 반환한다. 어차피 max 함수에서 무의미하게 처리된다.
9. 만약 현 위치가 도착점이 아니며 말이 없다면 현 위치를 pos_list와 pos_set 에 새로 새긴 new_pos_list와 new_pos_set을 다음 parameters로 하여 move 함수를 재개한다. 이때 현재 위치의 값을 누적값에 더하고, 이동횟수를 1 늘려주도록 한다.
10. move_cnt가 10이 되면 이 시점의 acc를 반환한다. 모두 이동의 종점을 찍은 결과들의 최댓값을 다시 상위로 올리므로 main에서는 이 함수의 시작점의 반환값을 출력하면 된다.

결과

맞았습니다!!

모범답안

출처

# empty