17825. 주사위 윷놀이 문제 바로가기
해결 방법
참고 tip)
제출 후 11%에서 틀린 경우에 문제 지문 중
말이 이동을 마치는 칸에 다른 말이 있으면 그 말은 고를 수 없다.이 부분에 대한 조건을 탄탄하게 해주면 된다. 11 %에서 틀렸을 때 30의 위치가 점수판에 2개인 것을 알고 분기를 다시 해줬습니다.제출 후 29%에서 틀린 경우에도 앞서 문제가 되었던
다른 말이 있으면 그 말은 고를 수 없다이부분에 대해 더 고려해야 합니다.반례
5 5 5 5 5 1 1 1 1 1 (입력시 167이 나와야합니다)
이 반례를 해결하고 나서 패스할 수 있었습니다.
주요 과정
점수판을 저장하기 위해서 road라는 리스트를 이용했습니다.
- road[0] : 남색, 가장 바깥 테두리 부분의 길 (파란색 칸에 도착한 적 X)
- road[1] : 주황색, 점수 10의 파란색 칸에 도달했을 때 도착지까지 남은 길
- road[2] : 초록색, 점수 20의 파란색 칸에 도달했을 때 도착지까지 남은 길
- road[0] : 노란색, 점수 30의 파란색 칸에 도달했을 때 도착지까지 남은 길
재귀함수를 이용하여 완전 탐색을 해주었습니다.
play 함수에 대한 과정
for문을 통해 모든 말이 해당 주사위만큼 움직였을 때를 완전탐색했습니다.
해당 말이 도착칸에 있는 말인지 체크하기
도착칸에 있지 않는 말일 경우 주사위만큼 움직이기
움직인 말이 파란색 칸 위에 있는지 확인하기
파란색 칸이면 road와 말의 위치 변경하기
road가 바뀌었기에 해당하는 road의 수로 바꾸고
말의 위치는 새로운 road의 첫번째 인덱스부터 갈 것이기에 0으로 설정하기
도착지점에 온 말인지 체크하기
- 도착지점에 온말이면 점수를 더하지 않고 말이 도착했다는 표시와 함께 다음 턴이 동작하도록 하기
도착지점에 온 말이 아니라면!! 너무 중요 ★
이동해도 되는지 확인하기 → 이동하려는 칸에 말이 있는지 확인한다!!!
이때 이동 가능하면 이동한 칸의 점수를 더해주고 다음 턴으로, 그렇지 않으면 continue를 이용하여 말 이동시키지 않기!
구현한 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
from copy import deepcopy
def play(n, score, horse):
global max_score
if n == 10: # 모든 게임의 천이 끝난 종료 조건
if score > max_score:
max_score = score
return
# 4개의 말에 대해 각각 이동을 시킴으로써 완전 탐색을 진행하기
for h in range(4):
if horse[h][0] != -1: # 도착칸에 있는 말이 아닌 경우
temp = deepcopy(horse)
temp[h][0] += dice[n] # 주사위만큼 이동하기
# 파란칸 위인지 확인하기
if temp[h][1] == 0:
if temp[h][0] == 5: # 점수가 10인 지점
temp[h][1] = 1 # road[1]의 길을 가기 때문에
temp[h][0] = 0
elif temp[h][0] == 10: # 점수가 20인 지점
temp[h][1] = 2 # road[2]의 길을 가기 때문에
temp[h][0] = 0
elif temp[h][0] == 15: # 점수가 30인 지점
temp[h][1] = 3 # road[3]의 길을 가기 때문에
temp[h][0] = 0
# 도착지점에 온 말인지 체크하기
if temp[h][0] >= len(road[temp[h][1]]):
temp[h][0] = -1 # 말이 도착했다고 체크하기
play(n + 1, score, temp)
else:
# 이동하려는 곳에 말이 있으면 이동하지 않는다! ★
frag = False # 이동하려는 칸에 말이 있는지 체크할 변수
visit = road[temp[h][1]][temp[h][0]] # 움직이려는 말이 있는 점수판의 점수
for v in range(len(temp)):
if temp[v][0] == -1: continue # temp[v][1]로 잘못 써서 26%에서 틀렸었다..!! 조심하기
if v != h and visit == road[temp[v][1]][temp[v][0]]:
if visit == 30: # 30의 경우 road에 여러개가 있기에 같은 위치인지 분기를 잘 해야한다.
if temp[h] == [0, 3] and temp[v] == [0, 3]:
frag = True
break
elif temp[h] != [0, 3] and temp[v] != [0, 3]:
frag = True
break
# len(road) = 4개의 길 중 해당 숫자는 2개 겹치기에 같은 위치인지 확인하기
elif visit in [16, 22, 24, 26, 28]:
if temp[h] == temp[v]:
frag = True
break
else: # 그 외의 숫자는 게임판에 각 1개 이기에 같기만 하면 같은 위치라 볼 수 있다.
frag = True
break
if frag: # 이동하려는 칸에 다른 말이 있기에 스킵하기
continue
play(n + 1, score + road[temp[h][1]][temp[h][0]], temp)
# road : 게임판의 점수를 저장한 리스트
# road[0] : 가장 바깥 테두리 부분의 길 (파란색 칸에 도착한 적 X)
# road[1] : 점수 10의 파란색 칸에 도달했을 때 도착지까지 남은 길
# road[2] : 점수 20의 파란색 칸에 도달했을 때 도착지까지 남은 길
# road[0] : 점수 30의 파란색 칸에 도달했을 때 도착지까지 남은 길
road = [
[i * 2 for i in range(21)],
[10, 13, 16, 19, 25, 30, 35, 40],
[20, 22, 24, 25, 30, 35, 40],
[30, 28, 27, 26, 25, 30, 35, 40]
]
max_score = 0 # 최대 점수로 출력값
horse = [[0, 0] for _ in range(4)] # 4개의 말에 대한 정보를 저장할 리스트
# horse 리스트안에 요소의 의미 : [해당 road에 대한 인덱스(위치), 어떤 road인지]
dice = list(map(int, input().split()))
play(0, 0, horse) # 모든 경우의 윷놀이를 진행할 함수
print(max_score)