[백준] 17825 주사위윷놀이 python 시간단축 풀이

문제로 이동

---

---

이 문제의 핵심

1. 윷놀이 맵을 어떻게 구현할 것인가?

2. 두가지 루트로 이동을 어떻게 할 것인가?

시간 단축

윷놀이 맵을 어떻게 구현할 것인가에 따라 달라졌습니다.

어떻게보면 당연한 말이지만 O(1)로 다음 위치를 판단하게 할 것인지 아니면 재귀함수를 사용해 (마치 LinkedList처럼) 다음 위치를 판단하게 할 것인지 고민했습니다.

여러 시도 끝에 O(1)이 가장 빠른 속도를 보였습니다.

그 과정을 이 글에서 설명합니다.

 

1차 시도 (968ms)

# 출발,도착 포함 33개 / 자식 index, 자신 점수
field = [[0, 0]] * 33

def init_field():
    global field
    for i in range(0, 21):
        field[i] = [[i + 1, i * 2]]
    field[5].append([22, 13])
    field[22], field[23], field[24] = [[23, 13]], [[24, 16]], [[25, 19]]
    field[10].append([26, 20])
    field[26], field[27] = [[27, 22]], [[25, 24]]
    field[15].append([28, 30])
    field[28], field[29], field[30] = [[29, 28]], [[30, 27]], [[25, 26]]
    field[25], field[31], field[32] = [[31, 25]], [[32, 30]], [[20, 35]]
    field[21] = [[-1, 0]]

def move(current_position, move_count, first_move):
    if move_count == 0 or current_position == 21:
        return current_position
    if first_move and len(field[current_position]) == 2:  # 지름길 있는 경우
        return move(field[current_position][1][0], move_count - 1, False)
    return move(field[current_position][0][0], move_count - 1, False)

각 칸별로 자식 노드를 적어주어 마치 트리와 유사한 모양을 구현했고, move 함수를 이용해 주사위 결과에 따라 다음 위치를 판단했습니다.

 

2, 3차 시도 (1132ms ~ 852ms)

한 함수에서 여러 함수를 호출하는 구조로 구현했는데, 이를 제거하고 하나의 함수에서 돌아갈 수 있도록 구현했습니다.

하지만 시간적으로 큰 차이가 없는 것으로 보아 영향이 없는 것을 알 수 있었습니다.

 

4차 시도 (480ms)

눈에 띄게 속도가 빨라졌습니다.

1차 시도때와 달리 윷놀이 필드 구성을 완전히 바꿨습니다.

 

N번 인덱스에서 갈 수 있는 모든 인덱스를 Array에 담아주는 구조로 구현을 했고 (단순 노가다)

단순하게 인덱스로 O(1)로 접근을 할 수 있으니 이동을 담당하는 move 함수도 필요 없어졌습니다.

 

# 출발,도착 포함 33개 / 자식 index, 자신 점수
field = {}
horses = [0, 0, 0, 0]
scores = []


def init_field():
    global field, scores
    scores = [0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 0, 13, 16, 19, 25, 22, 24,
              28, 27, 26, 30, 35]
    field = {}
    for i in range(21):
        lst = []
        for j in range(5):
            if i + j + 1 >= 21:
                lst.append(21)
                break
            else:
                lst.append(i + j + 1)
        field[i] = lst
    root1 = [5, 22, 23, 24, 25, 31, 32, 20, 21]
    root2 = [10, 26, 27, 25, 31, 32, 20, 21]
    root3 = [15, 28, 29, 30, 25, 31, 32, 20, 21]
    for i in range(len(root1)): field[root1[i]] = root1[i + 1:i + 6]
    for i in range(len(root2)): field[root2[i]] = root2[i + 1:i + 6]
    for i in range(len(root3)): field[root3[i]] = root3[i + 1:i + 6]

---

결론

SWEA처럼 여러 TC를 한 번에 실행하는 구조는 O(1)로 구현하는 것이 좋겠다는 생각을 했습니다.

추가로, 이 문제는 단순 시뮬레이션이기 때문에 러프하게 구현해도 상관 없겠다고 생각이 들었고

800ms에서 400ms로 줄었다는 것은 그 만큼 재귀 함수 호출에서 굉장히 많은 시간을 소요한다는 것을 알게되었습니다.

---

소스코드(Python3)

arr = list(map(int, input().split()))

# 출발,도착 포함 33개 / 자식 index, 자신 점수
field = {}
horses = [0, 0, 0, 0]
scores = []


def init_field():
    global field, scores
    scores = [0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 0, 13, 16, 19, 25, 22, 24,
              28, 27, 26, 30, 35]
    field = {}
    for i in range(21):
        lst = []
        for j in range(5):
            if i + j + 1 >= 21:
                lst.append(21)
                break
            else:
                lst.append(i + j + 1)
        field[i] = lst
    root1 = [5, 22, 23, 24, 25, 31, 32, 20, 21]
    root2 = [10, 26, 27, 25, 31, 32, 20, 21]
    root3 = [15, 28, 29, 30, 25, 31, 32, 20, 21]
    for i in range(len(root1)): field[root1[i]] = root1[i + 1:i + 6]
    for i in range(len(root2)): field[root2[i]] = root2[i + 1:i + 6]
    for i in range(len(root3)): field[root3[i]] = root3[i + 1:i + 6]


def dfs(depth, score):
    global arr, horses
    if depth == 10:
        return score
    dice = arr[depth]
    max_score = score
    for i in range(4):
        # 이미 끝에 도달한 말
        if horses[i] == 21:
            continue
        next_index = 0
        if len(field[horses[i]]) < dice:  # 끝에 도달한다는말
            next_index = 21
        else:
            next_index = field[horses[i]][dice-1]
        if next_index in horses and next_index != 21:
            continue
        cur_index = horses[i]
        horses[i] = next_index
        max_score = max(max_score, dfs(depth + 1, score + scores[next_index]))
        horses[i] = cur_index
    return max_score


def game():
    answer = dfs(0, 0)
    print(answer)


init_field()
game()