[삼성역량테스트] 17825 주사위윷놀이

풀이일시 : 2021-03-13

 

문제 : 

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

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

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

 

 

 

입력 : 

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

 

ex)

1 2 3 4 1 2 3 4 1 2

 

 

출력 : 

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

 

ex)

190

 

 

풀이 및 코드 : 

 

처음 이 문제를보고 하드코딩으로 구현해주면 되겠다고 생각하고 바로 코드를 작성한 것은 오판이었다.

 

우선 생각을 하고 map 을 디자인 해 주는 과정이 필요했다.

 

• 포인트맵을 map 배열로 생성해주었다.
• 방향전환이 되는 네 개의 노드에 대한 turn배열을 생성해주었다.
• 각각의 점수를 score 배열을 선언해 관리해주었다.
• 각각의 노드에 말이 존재하는지를 check를 통해 관리해주었다.
• DFS, backtracking 이용하여 최대값이 갱신된다면 저장해주고 계속하여 전체 과정을 보며 풀이한다.

 

코드의 주석으로 설명을 대체한다.

 

#include <iostream>

using namespace std;

int arr[10];
int mal[4];
int map[35]; //다음 이동할 노드 번호를 저장
int turn[35]; //방향전환되는 10,20,30 을 관리
int check[35]; //해당 노드에 말이있는지 여부
int score[35]; //각 노드의 점수를 관리
int ans = 0;

void setting() {
	for (int i = 0; i < 21; i++) {
		map[i] = i + 1;
	}
	map[21] = 21;
	for (int i = 22; i < 27; i++) {
		map[i] = i + 1;
	}
	map[28] = 29;
	map[29] = 30;
	map[30] = 25;
	map[31] = 32;
	map[32] = 25;
	map[27] = 20;
	turn[5] = 22;
	turn[10] = 31;
	turn[15] = 28;
	turn[25] = 26;
	for (int i = 0; i < 21; i++) {
		score[i] = i * 2;
	}
	score[22] = 13;
	score[23] = 16;
	score[24] = 19;
	score[31] = 22;
	score[32] = 24;
	score[28] = 28;
	score[29] = 27;
	score[30] = 26;
	score[25] = 25;
	score[26] = 30;
	score[27] = 35;
}

void dfs(int cnt, int sum) {
	//종료조건을 만들어준다
	if (cnt == 10) { //열번의 움직임을 다 수행했고
		if (sum > ans) //큰값으로 갱신
			ans = sum;
		return; //반환
	}
	//웬만하면 0을 수행하나 그게아니면 1,2,3번말을 움직이도록
	for (int i = 0; i < 4; i++) {
		int prev = mal[i]; //현재의 말
		int now = prev;
		int move = arr[cnt]; //몇칸이나 움직일지
		if (turn[now] > 0) { //turn하는 칸이면
			now = turn[now]; //현재 위치를 turn 한다
			move -= 1;
		}
		//움직이는 만큼 while문 돌려준다.
		while (move--) {
			now = map[now];
		}
		if (now != 21 && check[now] == true) //이미 차있는 곳이면서 도착지점이 아니면 다른 말을 사용한다
			continue;
		check[prev] = false;
		check[now] = true;
		mal[i] = now;

		dfs(cnt + 1, sum + score[now]);
		//백트래킹
		mal[i] = prev;
		check[prev] = true;
		check[now] = false;
	}
}

int main() {
	setting();
	// 주사위 입력 받기
	for (int i = 0; i < 10; i++) {
		cin >> arr[i];
	}
	dfs(0, 0);
	cout << ans << '\n';
	return 0;
}

 

참고자료 : backtracking

dbstndi6316.tistory.com/37

[개념정리] Backtracking 백트래킹