[백준 17825번] 주사위 윷놀이

문제 보기

이 문제는 브루트 포스 문제이다.

이 문제는 2019년 삼성 하반기 SW 역량 테스트에서 나온 두 번째 문제이다.

문제를 푸는데 3일이나 걸렸다... (도움을 주신 정인준 선배님 감사합니다ㅠㅠ)

지금 와서 되돌아보니 풀이의 큰 흐름은 맞았지만, 문제에서 간과하기 쉬운 조건들이 있었다.

이제는 삼성 SW 역량 테스트에서 알고리즘의 구현을 할 수 있는지 묻는 게 아니라, 문제 속에 찾기 힘든 조건들을 포함시키는 게 요즘 추세인 것 같다.

 

먼저, 백준에 나와있는 윷놀이 판의 그림은 헷갈리는 부분이 있으므로 이를 명확하게 하기 위해서 다음의 그림을 참고하면 좋을 것 같다.

윷놀이 판

위와 같은 윷놀이 판에서, 모든 경우의 수를 따져야 하므로 말이 지나갈 경로를 정해야 한다. 경로를 어떻게 구성하고 구현할지는 사람마다 다르겠지만, 나는 다음과 같이 구현하였다.

0번 경로

1번 경로

2번 경로

3번 경로

4번 경로

이와 같은 경로는 코드의 4~10번째 줄에 선언되어 있다.

 

나는 브루트 포스를 DFS로 구현하였는데, 문제를 푼 로직은 다음과 같다.

1. 각 턴마다 말이 움직일 횟수를 가져온다. (24~25번째 줄)
2. 현재 위치를 구하고, 만약 현재 위치가 도착지점이라면 다음 말로 넘어간다.(= 다음 말을 이동시킨다.) (32~34번째 줄)
3. 각 말마다 다음 위치를 구하고, 그다음 위치가 만약 각 코너와 중앙이라면, 이동할 경로의 번호와 위치를 바꿔준다. (36~56번째 줄)
4. 만약 말의 다음 위치가 도착을 넘어간다면, 도착에서 이동을 마친다. (58~60번째 줄)
5. 시작과 도착을 제외하고, 만약 현재 말의 다음 위치에 이미 다른 말이 있다면, 다음 말로 넘어간다.(= 다음 말을 이동시킨다.) (62~66번째 줄)
6. 모든 조건을 통과하고 난 후, 말을 이동시킨다. (68~71번째 줄)
7. DFS를 통해 모든 경우를 재귀적으로 탐색한다. (73번째 줄)
8. 이동시킨 말을 다시 원래 위치로 되돌린다. (75~78번째 줄)

 

3번 과정에서 내가 빠트렸던 점은, 0번 경로에서 40번 위치로 이동할 때, 4번 경로의 40번으로 위치 변경을 시켜주지 않았던 것이다.

따라서 5번 과정에서, 실질적으로 0번 경로의 40번과 4번 경로의 40번은 같은 위치지만, 다른 위치로 판단하여 같은 위치에 말이 2개 있을 수 있었다.

이 문제에서 신경 써야 할 점은 DFS로 브루트 포스를 구현하는 것이 아니라, 말 그대로 윷놀이 게임을 어떻게 구현할지 그 조건을 잘 찾아내는 게 중요한 것 같다.

 

예제 입력으로도 찾기 힘든 반례가 있다면 다음을 참고하면 좋을 것 같다.

Input:

3 5 2 5 3 5 2 1 3 1

Output:

246

다음의 말들을 순서대로 움직이면 위의 결과를 얻을 수 있다.

1 2 2 1 1 1 1 1 2 1

 

import sys

movements = list(map(int, sys.stdin.readline().split()))
path_info = [
	[0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 0],
	[10, 13, 16, 19, 25],
	[20, 22, 24, 25],
	[30, 28, 27, 26, 25],
	[25, 30, 35, 40, 0]
]
# [i-th path, j-th block]
piece_positions = [[0, 0], [0, 0], [0, 0], [0, 0]]
piece_scores = [0, 0, 0, 0]
answer = 0


def dfs(idx):
	# termination condition
	if idx == 10:
		global answer
		answer = max(answer, sum(piece_scores))
		return answer
	
	# how many steps are going to be moved
	move = movements[idx]
	
	for i in range(4):
		# current piece position
		cur_path = piece_positions[i][0]
		cur_block = piece_positions[i][1]
		
		# if current piece finished the game
		if cur_block == len(path_info[cur_path]) - 1:
			continue
		
		next_path = cur_path
		next_block = cur_block + move
		# change path at the corner
		if cur_path == 0:
			if next_block == 5:
				next_path = 1
				next_block = 0
			elif next_block == 10:
				next_path = 2
				next_block = 0
			elif next_block == 15:
				next_path = 3
				next_block = 0
			elif next_block == 20:
				next_path = 4
				next_block = 3
		# change path at the center point
		elif cur_path < 4:
			if next_block >= len(path_info[cur_path]) - 1:
				next_path = 4
				next_block -= len(path_info[cur_path]) - 1
		
		# limit block to the last block of the path
		if next_block >= len(path_info[next_path]):
			next_block = len(path_info[next_path]) - 1
		
		# without the first & last block
		if path_info[next_path][next_block] != 0:
			# if next step is already taken
			if [next_path, next_block] in piece_positions:
				continue

		# move piece and update information
		piece_positions[i][0] = next_path
		piece_positions[i][1] = next_block
		piece_scores[i] += path_info[next_path][next_block]
		
		dfs(idx + 1)
		
		# reset piece and information
		piece_positions[i][0] = cur_path
		piece_positions[i][1] = cur_block
		piece_scores[i] -= path_info[next_path][next_block]


dfs(0)
print(answer)