주사위 윷놀이 - 17825 - C++

해당 문제는 이 글을 보고 풀었습니다.

문제 흐름 요약

만약 3번의 주사위를 던지고 말이 2개있다면

그림과 같이 1번 말이 3번 움직이는경우, 2번 움직이고 2번말이 1번움직이는 경우 이런식으로 진행될것이다.
3번 움직인 다음, 2번 움직이고 2번말을 움직여야한다는 점에서 BackTracking인것을 확인했다.

그럼 진짜 backtracking으로 풀어도되나?
주사위를 10번 던지는데 말의 갯수는 4개이다. 그러면 경우의수가 4^10이고 2^20이니까 1048576가지 경우의수가 나온다. 시간내에 충분히 풀 수 있다.

문제 1.

2->4->6 번 이런식으로 노드를 탐색하는 방법은 그전에 유니온 파인드에서도 해봤다. 인덱스 2번의 배열 값에 다음 움직일 4번을 넣으면 된다.
그런데 이렇게 했더니 문제가 있다.

그림과 같은 16번 노드일때, 18번으로 갈지 19번으로 갈지 값에 뭘 넣어야할지 모르기 때문이다.

고로 처음에 어떻게 생각했냐면, 노드를 LinkedList형태로 풀라고했다.

int dice[10];
int Max = 0;
struct Node {
    int num;        // 데이터 변수
    Node* next_black;
    Node* next_blue;     // 다음 노드를 가리킬 포인터

    // 생성자 (선택 사항)
    Node(int value) : num(value), next_blue(nullptr), next_black(nullptr) {}
};

void init() {
    //주사위 받기
    for (int i = 0; i < 10; i++) {
        int tmp = 0;
        cin >> tmp;
        dice[i] = tmp;
    }

    Node* head = new Node(0);
    Node* cur = head;

    //2 ->4 -> 6... ->40까지 연결
    for (int i = 2; i <= 42; i += 2) {
        cur->next_black = new Node(i);
        cur = cur->next_black;
    }

    Node * end = cur;

    Node * twentiyfive = new Node(25);

    //10에서 25까지 가는 노드 연결
    cur = head;
    while (cur->num != 10) {
        cur = cur->next_black;
    }

    //13노드
    for (int i = 13; i <= 19; i += 3){
        cur->next_blue = new Node(i);
        cur = cur->next_blue;
    }
    //19번노드->25번노드 연결
    cur->next_black = twentiyfive;

    //20에서 25번 가는 노드 연결
    cur = head;
    while (cur->num != 20) {
        cur = cur->next_black;
    }

    //22번노드
    for (int i = 22; i <= 24; i += 2) {
        cur->next_blue = new Node(i);
        cur = cur->next_blue;
    }

    //24번과 25번 연결
    cur->next_black = twentiyfive;

    //30번 출발 연결
    cur = head;
    while (cur->num != 30) {
        cur = cur->next_black;
    }

    //28번노드
    for (int i = 28; i >= 26; i--) {
        cur->next_blue = new Node(i);
        cur = cur->next_blue;
    }

    //26번과 25번 연결
    cur->next_black = twentiyfive;


    //마지막으로 25번과 40번 연결
    //40번 노드 찾기
    cur = head;
    while (cur->num != 40) {
        cur = cur->next_black;
    }

    for (int i = 30; i <= 35 ; i+=5) {
        twentiyfive->next_blue = new Node(i);
        twentiyfive = twentiyfive->next_blue;
    }

    //마지막으로 35과 40번 연결,40과 42연결
    twentiyfive->next_blue = cur;
    cur->next_black = end;

}

이렇게 설정해서 만약 출발 노드가 10,20,30이라면 BT할때 color를 blue로 해서 if문을 통해 color가 blue라면 next_blue로 노드를 이동시키는 방식으로 구현하려고 했다.

문제점

1. 구현이 너무 어렵다
2. 만약 현재 위치가 14번이라면, 14에서 16으로 이동하기위해서 시작노드부터 14번 노드까지 이동한 후에, 그다음 14번노드에서 16번으로 이동해야하는 번거로움이 있다.

그래서 문제를 풀지 못했다.

해결법

문제의 핵심은 주사위의 숫자는 1이상이라는것이다. 고로 10,20,30에서 출발한다면 일단 그다음 노드로 최소 한칸은 이동해야 한다는 것이다.

그러면 아까 문제는 16번노드가 두개로 겹치기 때문에 문제가 생겼다. 그러면 겹치지 않게 바꿔주면된다.

출처[블로그]

그러고나서, 5번노드에서 22번노드로 가는경우에는 어차피 1번은 이동을해야하니까 next값을 22로 설정하면된다. 그 다음 이동횟수 만큼 이동하면 된다.

	//10 20 30에서 파랑색 방향
	turn[5] = 22;
	turn[10] = 31;
	turn[15] = 28;
    
    //어차피 주사위는 한번은 굴림 파랑색에서 출발시 한칸 먼저 움직이기
		if (turn[current_pos] > 0) {
			move--;
            //만약 current_pos가 5라면 next_pos는 22가됌
			next_pos = turn[current_pos];
		}

정답코드

#include <string>
#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int map[34];
int score[34];
int turn[34];
bool check[34];
int position[4];
int dice[10];

int Max = 0;

void init() {
	//다이스 받기
	for (int i = 0; i < 10; i++) {
		int tmp = 0;
		cin >> tmp;
		dice[i] = tmp;
	}
	//바깥쪽 설정 인덱스 0번에 다음에 갈 1번이저장되어있음
	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[27] = 20;

	map[28] = 29; map[29] = 30; map[30] = 25;
	map[31] = 32; map[32] = 25;

	//10 20 30에서 파랑색 방향
	turn[5] = 22;
	turn[10] = 31;
	turn[15] = 28;

	//점수판 갱신
	for (int i = 0; i < 21; i++) {
		score[i] = i * 2;
	}
	score[22] = 13; score[23] = 16; score[24] = 19;
	score[25] = 25; score[26] = 30; score[27] = 35;
	score[28] = 28; score[29] = 27; score[30] = 26;
	score[31] = 22; score[32] = 24;
}

void dfs(int cnt, int num) {
	if (cnt == 10) {
		if (num > Max)Max = num;
		return;
	}

	//4개의 말 확인
	for (int i = 0; i < 4; i++) {
		int move = dice[cnt];
		int current_pos = position[i];
		int next_pos = current_pos;
		//어차피 주사위는 한번은 굴림 파랑색에서 출발시 한칸 먼저 움직이기
		if (turn[current_pos] > 0) {
			move--;
			next_pos = turn[current_pos];
		}

		//움직이기
		while (move > 0) {
			move--;
			next_pos = map[next_pos];
		}

		if (next_pos == 21 || !check[next_pos]) {
			//cout << next_pos << " ";
			position[i]=next_pos;
			check[current_pos] = false;
			check[next_pos] = true;

			dfs(cnt + 1, num + score[next_pos]);

			position[i]=current_pos;
			check[current_pos] = true;
			check[next_pos] = false;
		}
	}
	
}

int main() {
	init();
	dfs(0,0);
	cout << Max;
}