문제
주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다.
- 처음에는 시작 칸에 말 4개가 있다.
- 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면 파란색 화살표를 타야 하고, 이동하는 도중이거나 파란색이 아닌 칸에서 이동을 시작하면 빨간색 화살표를 타야 한다. 말이 도착 칸으로 이동하면 주사위에 나온 수와 관계 없이 이동을 마친다.
- 게임은 10개의 턴으로 이루어진다. 매 턴마다 1부터 5까지 한 면에 하나씩 적혀있는 5면체 주사위를 굴리고, 도착 칸에 있지 않은 말을 하나 골라 주사위에 나온 수만큼 이동시킨다.
- 말이 이동을 마치는 칸에 다른 말이 있으면 그 말은 고를 수 없다. 단, 이동을 마치는 칸이 도착 칸이면 고를 수 있다.
- 말이 이동을 마칠 때마다 칸에 적혀있는 수가 점수에 추가된다.
주사위에서 나올 수 10개를 미리 알고 있을 때, 얻을 수 있는 점수의 최댓값을 구해보자.
입력
첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다.
출력
얻을 수 있는 점수의 최댓값을 출력한다.
예제 입력 1
1 2 3 4 1 2 3 4 1 2
예제 출력 1
190복기
1. 삼성 기출이라는 너무 어렵네.. 일단 문제를 읽고 어떻게 풀어야할지 감도 안 왔다.
2. 백트래킹이 중요한데 아직 내가 잘 못하는거 같아.
솔루션
# graph[i]: 노드 i에서 다음으로 이동가능한 노드
graph = [[1], # 0 -> 2
[2], # 2 -> 4
[3], # 4 -> 6
[4],[5], [6,21], # 10에 해당하는 노드
[7], [8], [9], [10],
[11, 25], [12], [13], [14], [15],
[16, 27], [17], [18], [19], [20],
[32], [22], [23], [24], [30],
[26], [24], [28], [29], [24],
[31], [20], [32]]
# 각 노드의 점수
score = [0, 2, 4, 6, 8,
10, 12, 14, 16, 18,
20, 22, 24, 26, 28,
30, 32, 34, 36, 38,
40, 13, 16, 19, 25,
22, 24, 28, 27, 26,
30, 35, 0]
dice = list(map(int, input().split()))
def backtracking(depth, result, horses, answer):
if depth == 10:
answer[0] = max(answer[0], result) # 최대 점수 갱신
return
for i in range(4): # 말 4개
if horses[i] == 32: # 이미 도착한 말은 이동 불가
continue
x = horses[i] # 현재 말 위치
move_count = dice[depth] # 주사위 값
is_blue = len(graph[x]) == 2 # 파란 길 여부
# 주사위 값만큼 이동
for j in range(move_count):
if x == 32: # 이미 도착 칸이면 중단
break
if j == 0 and is_blue: # 첫 이동이 파란 길인 경우
x = graph[x][1]
else: # 나머지 이동은 빨간 길
x = graph[x][0]
# 목적지에 도착했거나, 다른 말이 없는 위치라면
if x == 32 or (x < 32 and x not in [horses[k] for k in range(4) if k != i]):
before = horses[i] # 이전 말 위치 저장
horses[i] = x # 현재 말 위치 갱신
backtracking(depth + 1, result + score[x], horses, answer)
horses[i] = before # 상태 복구
# 초기 호출
answer = [0] # mutable 객체로 최대 점수 저장
backtracking(0, 0, [0, 0, 0, 0], answer)
print(answer[0])
댓글