1. 문제

---

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

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

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

제한 사항

시간 : 2 초
메모리 : 512 MB

입력

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

출력

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

- 키워드

• 백트래킹을 하면서 말의 위치를 저장할 때 주의에 주의에 주의를 기울이자.
• 테스트를 할 때 왜 틀린지 모르겠다면 stack을 사용해 말의 이동 순서를 체크해보자.

2. 풀이

---

이 문제를 풀 때, 상당히 골치가 아팠던 거 같다.

문제가 쉽다고 하면 쉽지만, 한 번 삐끗하면 미궁속으로 빠지기 쉬운 문제같다.

미궁속으로 빠지게 하는 원인은 바로 이 부분이다.

해당 부분이 게임판에서 위치를 저장하기 상당히 까다로운 부분이다.

먼저 해당 게임판을 2차원 배열로 만들면 다음과 같이 나온다.

그리고 겹치는 부분이 다음과 같다.

end의 경우 최고점을 계산하는데 영향을 주지 않기 때문에 위치만 기억하면 된다.

겹치는 부분에서도 같은 점수에 다른 위치인 30이 있으므로 잘 구별해야한다.

해당 문제에서는 테스트케이스 과정을 설명하기보단, 문제의 접근 방법을 작성하는 것이 바람직해 보인다.

먼저, 해당 문제에서 게임판과 게임판의 점수와 같은 크기의 배열을 하나 더 만든다.

board = []
board.append([2*i for i in range(21)] + [0])
board.append([10,13,16,19,25,30,35,40,0])
board.append([20,22,24,25,30,35,40,0])
board.append([30,28,27,26,25,30,35,40,0])
log = []
for i in range(4):
	log.append([0]*len(board[i]))

board의 경우 위 사진과 같은 게임판이고

log의 경우 말의 위치를 저장하는 배열이다.

그렇다면 우리는 겹치는 부분인 10, 20, 25, 30, 35, 40을 해결해야 한다.

말이 이동할 때 지금 말의 위치에 따라 저장하는 방식을 나누도록 한다.

def equal(unit,state): # unit은 말, state는 0일 때는 지우고, i일 때 해당 위치에 저장
	load, idx = unit # 말의 경로와 위치
	if load == 0: # 말이 첫 번째 경로에 해당할 경우
		if idx == 5:
			log[0][5] = log[1][0] = state
		elif idx == 10:
			log[0][10] = log[2][0] = state
		elif idx == 15:
			log[0][15] = log[3][0] = state
		elif idx == 20:
			log[0][-2] = log[1][-2] = log[2][-2] = log[3][-2] = state
		else:
			log[0][idx] = state

	elif load == 1: # 말이 두 번째 경로에 해당할 경우
		if idx == 0:
			log[0][5] = log[1][0] = state
		elif idx == 4:
			log[1][4] = log[2][3] = log[3][4] = state
		elif idx == 5:
			log[1][5] = log[2][4] = log[3][5] = state
		elif idx == 6:
			log[1][6] = log[2][5] = log[3][6] = state
		elif idx == 7:
			log[0][-2] = log[1][7] = log[2][6] = log[3][7] = state
		else:
			log[1][idx] = state

	elif load == 2: # 말이 세 번째 경로에 해당할 경우
		if idx == 0:
			log[0][10] = log[2][0] = state
		elif idx == 3:
			log[1][4] = log[2][3] = log[3][4] = state
		elif idx == 4:
			log[1][5] = log[2][4] = log[3][5] = state
		elif idx == 5:
			log[1][6] = log[2][5] = log[3][6] = state
		elif idx == 6:
			log[0][-2] = log[1][7] = log[2][6] = log[3][7] = state
		else:
			log[2][idx] = state

	elif load == 3: # 말이 네 번째 경로에 해당할 경우
		if idx == 0:
			log[0][15] = log[3][0] = state
		elif idx == 4:
			log[1][4] = log[2][3] = log[3][4] = state
		elif idx == 5:
			log[1][5] = log[2][4] = log[3][5] = state
		elif idx == 6:
			log[1][6] = log[2][5] = log[3][6] = state
		elif idx == 7:
			log[0][-2] = log[1][7] = log[2][6] = log[3][7] = state
		else:
			log[3][idx] = state

state를 i+1로 설정한 이유는 log를 확인할 때, 몇 번말이 어디에 있는지 확인하기 위함이다.

말이 이동할 때, 해당 위치를 지울 때 1번 그리고 이동할 위치에 저장할 때 1번 총 2번 사용하면 된다.

지울 때는 state에 0을, 이동한 위치를 저장할 때는 state에 i+1을 넣는다.

그리고 다른 경우의 수를 탐색하기 위해서 다시 2번 반대로 사용하면 된다.

다음은 백트래킹 과정이다.

memory = []

def search(dice,now,answer,units,score):
	# dice는 입력 값, now는 몇 번째 이동인가?, answer의 경우 정답
    # units는 말 4개의 경로와 위치가 저장된 배열, score는 현재까지 이동할 때 점수의 총합
	if now == 10: # 모든 이동을 마쳤을 때 최대값이면 저장한다.
		answer[0] = max(answer[0],score)
	else:
		for i in range(4):
			load, idx = units[i]
			before = [load,idx] # 이동하기 전 위치를 저장한다. load는 경로 idx는 위치이다.
			if dice[now]+idx >= len(board[load]): # end보다 멀리 이동일 경우
				units[i][1] = len(board[load])-1 # end에 위치를 고정
				equal(before,0)
				equal(units[i],i+1)
                # memory.append(i+1)
				search(dice,now+1,answer,units,score+board[units[i][0]][units[i][1]])
				# memory.pop()
                equal(units[i],0)
				equal(before,i+1)
				units[i] = before
			elif dice[now]+idx < len(board[load]) and log[load][dice[now]+idx] == 0:
            # 경로 내의 이동
				units[i][1] += dice[now] # 위치를 이동시키고
				equal(before,0) # 이전 위치를 초기화하고
				equal(units[i],i+1) # 현재 위치를 갱신한다
                # memory.append(i+1) # stack을 이용하여 말의 이동 순서를 저장
				if units[i][0] == 0 and units[i][1] == 5:
					units[i] = [1,0] # 10에 있는 말의 경로를 0에서 1로 바꿔준다.
				elif units[i][0] == 0 and units[i][1] == 10:
					units[i] = [2,0] # 20에 있는 말의 경로를 0에서 2로 바꿔준다. 
				elif units[i][0] == 0 and units[i][1] == 15:
					units[i] = [3,0] # 30에 있는 말의 경로를 0에서 3으로 바꿔준다.
				search(dice,now+1,answer,units,score+board[units[i][0]][units[i][1]])
                # memory.pop() # 이전 경우의 수로 초기화
				equal(units[i],0) # 이동했던 위치를 초기화하고
				equal(before,i+1) # 이전 위치로 돌아가 갱신한다.
				units[i] = before # 말의 위치를 이전 위치로 다시 저장한다.

주석을 통해서 설명을 달아놨지만, memory의 존재가 왜 있는지 이유가 불충분하다.

해당 경우의 수의 각 말의 위치는

1번 말 : 35
2번 말 : 30
3번 말 : 40
4번 말 : start

이다.

하지만, 이 경우의 수가 어떤 순서로 왔는지는 알 방법이 없다.

그렇기 때문에 memory를 통해서 나중에 오답이 나왔을 경우 틀린 부분을 찾을 때 사용할 수 있다.

해당 테스트케이스는

5 4 5 2 2 2 5 3 1 4

이고,

answer를 저장하는 경우의 수중 하나고, 해당 테스트케이스의 정답은 245 다.

정리

1. log를 확인해서 위치가 잘 이동하고 저장이 되는지 확인한다.
2. 잘 모르겠을 경우 memory와 같이 이동 순서를 저장하는 stack을 통해 체크한다.
3. 보통 정답을 저장할 때 log, memory를 확인하면서 고쳐 나가면 된다.

3. 소스코드

---

import sys
input = sys.stdin.readline

board = []
board.append([2*i for i in range(21)] + [0])
board.append([10,13,16,19,25,30,35,40,0])
board.append([20,22,24,25,30,35,40,0])
board.append([30,28,27,26,25,30,35,40,0])
log = []
for i in range(4):
	log.append([0]*len(board[i]))

def equal(unit,state):
	load, idx = unit
	if load == 0:
		if idx == 5:
			log[0][5] = log[1][0] = state
		elif idx == 10:
			log[0][10] = log[2][0] = state
		elif idx == 15:
			log[0][15] = log[3][0] = state
		elif idx == 20:
			log[0][-2] = log[1][-2] = log[2][-2] = log[3][-2] = state
		else:
			log[0][idx] = state

	elif load == 1:
		if idx == 0:
			log[0][5] = log[1][0] = state
		elif idx == 4:
			log[1][4] = log[2][3] = log[3][4] = state
		elif idx == 5:
			log[1][5] = log[2][4] = log[3][5] = state
		elif idx == 6:
			log[1][6] = log[2][5] = log[3][6] = state
		elif idx == 7:
			log[0][-2] = log[1][7] = log[2][6] = log[3][7] = state
		else:
			log[1][idx] = state

	elif load == 2:
		if idx == 0:
			log[0][10] = log[2][0] = state
		elif idx == 3:
			log[1][4] = log[2][3] = log[3][4] = state
		elif idx == 4:
			log[1][5] = log[2][4] = log[3][5] = state
		elif idx == 5:
			log[1][6] = log[2][5] = log[3][6] = state
		elif idx == 6:
			log[0][-2] = log[1][7] = log[2][6] = log[3][7] = state
		else:
			log[2][idx] = state

	elif load == 3:
		if idx == 0:
			log[0][15] = log[3][0] = state
		elif idx == 4:
			log[1][4] = log[2][3] = log[3][4] = state
		elif idx == 5:
			log[1][5] = log[2][4] = log[3][5] = state
		elif idx == 6:
			log[1][6] = log[2][5] = log[3][6] = state
		elif idx == 7:
			log[0][-2] = log[1][7] = log[2][6] = log[3][7] = state
		else:
			log[3][idx] = state

def search(dice,now,answer,units,score):
	if now == 10:
		answer[0] = max(answer[0],score)
	else:
		for i in range(4):
			load, idx = units[i]
			before = [load,idx]
			if dice[now]+idx >= len(board[load]):
				units[i][1] = len(board[load])-1
				equal(before,0)
				equal(units[i],i+1)
				search(dice,now+1,answer,units,score+board[units[i][0]][units[i][1]])
				equal(units[i],0)
				equal(before,i+1)
				units[i] = before
			elif dice[now]+idx < len(board[load]) and log[load][dice[now]+idx] == 0:
				units[i][1] += dice[now]
				equal(before,0)
				equal(units[i],i+1)
				if units[i][0] == 0 and units[i][1] == 5:
					units[i] = [1,0]
				elif units[i][0] == 0 and units[i][1] == 10:
					units[i] = [2,0]
				elif units[i][0] == 0 and units[i][1] == 15:
					units[i] = [3,0]
				search(dice,now+1,answer,units,score+board[units[i][0]][units[i][1]])
				equal(units[i],0)
				equal(before,i+1)
				units[i] = before


def solution(dice):
	answer = [0]
	units = []
	for _ in range(4):
		units.append([0,0])
	search(dice,0,answer,units,0)

	return answer[0]

if __name__ == "__main__":
	dice = list(map(int,input().split()))
	print(solution(dice))

4. 후기

---

여러 경우의 수를 꼼꼼히 체크하는 사람이라면 이 문제를 풀기 쉽겠지만,

나처럼 실수가 잦은 사람은 예외 처리를 제대로 못하여 미궁속에 빠져 멘탈이 갈리는 경우가 있다.

그리고 나처럼 실수가 잦은사람이 많은지 해당 문제의 레벨은 골드 2다.

문제가 안 풀릴 때는 계속 붙잡지 말고, 다음 날 멘탈 회복한 상태서 다시 풀도록 하자.