이 문제의 핵심
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()