17825 주사위 윷놀이

www.acmicpc.net/problem/17825

17825번: 주사위 윷놀이

#include<stdio.h>
#include<iostream>
#include<vector>
#include<string.h>
#include<string>
using namespace std;
int cubeNum[11];//주사위 수 저장 배열
int D[33];//말의 순서 저장 배열
int ret;//최댓값 저장
struct Data {
	int idx,nextIdx,visitPreIdx;//현재 인덱스,다음 인덱스
}horse[4];//말
int board[33] = { 0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,0,
			13,16,19,25,
			22,24,
			28,27,26,
			30,35 };//맵 구성요소
void init() {
	ret = 0x80000000;
	memset(horse, 0, sizeof(horse));
	memset(cubeNum, 0, sizeof(cubeNum));//초기화
	memset(D, 0, sizeof(D));//초기화
	for (int i = 0; i < 10; i++) {
		scanf("%d", &cubeNum[i]);
	}
}
bool playGame(int &sum) {
	sum = 0;
	memset(horse, 0, sizeof(horse));
	int visit[33] = { 0, };//방문체크
	//마지막 인덱스가 이곳이면 다음 넘어갈곳
	/*5-22
	  25-31
	  27-25
	  30-25
	  32-20
	  20-21
	*/
	for (int i = 0; i < 10; i++) {
		for (int j = 0; j < cubeNum[i]; j++) {
			if (horse[D[i]].nextIdx == -1|| horse[D[i]].nextIdx == -2)break;//범위 넘어가는 경우 종료
			if (horse[D[i]].nextIdx != 0) {//파란원 부분인경우 그 범위로 이동 시키기
				horse[D[i]].idx = horse[D[i]].nextIdx;
				horse[D[i]].nextIdx = 0;
			}
			else  horse[D[i]].idx++;
			if (horse[D[i]].idx == 25)horse[D[i]].nextIdx = 31;//25점에서 30점가는 구간
			if(horse[D[i]].idx == 27|| horse[D[i]].idx == 30)horse[D[i]].nextIdx = 25;
			//19점에서 25점
			//24점에서 25점
			//26점에서 25점 가는 구간
			if (horse[D[i]].idx == 32)horse[D[i]].nextIdx = 20;//35점에서 40점 가는 구간
			if (horse[D[i]].idx == 20)horse[D[i]].nextIdx = 21;
			if (horse[D[i]].idx == 21) {
				horse[D[i]].nextIdx = -1;//도착구역 간것 체크
				break;
			}
		}
		if (horse[D[i]].idx == 5)horse[D[i]].nextIdx = 22;
		if (horse[D[i]].idx == 10)horse[D[i]].nextIdx = 26;
		if (horse[D[i]].idx == 15)horse[D[i]].nextIdx = 28;
		if (horse[D[i]].idx == 25)horse[D[i]].nextIdx = 31;
		if (horse[D[i]].idx == 27|| horse[D[i]].idx == 30)horse[D[i]].nextIdx = 25;
		if (horse[D[i]].idx == 32)horse[D[i]].nextIdx = 20;
		if (horse[D[i]].idx == 20)horse[D[i]].nextIdx = 21;


		if (visit[horse[D[i]].idx] == 0) {//현재 칸에 말이 있는지 확인
			if (horse[D[i]].idx == 21 && horse[D[i]].nextIdx == -1) {
				sum += board[horse[D[i]].idx];//이동 한 후 마지막칸의 값 저장
				if (horse[D[i]].visitPreIdx != 0) {//이전의 칸의 방문 지우기 위한 조건
					visit[horse[D[i]].visitPreIdx] = 0;
					horse[D[i]].visitPreIdx = 0;
				}
				horse[D[i]].nextIdx = -2;
			}
			if(horse[D[i]].idx != 21){
				sum += board[horse[D[i]].idx];//이동 한 후 마지막칸의 값 저장
				if (horse[D[i]].visitPreIdx != 0) {//이전의 칸의 방문 지우기 위한 조건
					visit[horse[D[i]].visitPreIdx] = 0;
					horse[D[i]].visitPreIdx = 0;
				}
				horse[D[i]].visitPreIdx = horse[D[i]].idx;//이전 인덱스 기록
				visit[horse[D[i]].idx] = 1;//방문 체크
			}
		}
		else return false;//놓은 칸에 말이 있는경우 제외 
	}
	return true;
}
void dfs(int idx,int d) {//순열 뽑아내기
	if (idx == 10) {//말의 순서 10개 뽑기
		int sum = 0;
		if (!playGame(sum)) return;
		ret = ret < sum ? sum : ret;
		return;
	}
	for (int i = 0; i < 4; i++) {
		D[idx] = i;
		dfs(idx + 1,d++);
		D[idx] = 0;
	}
}
int main(void) {
	int testCase = 1;
	//scanf("%d", &testCase);
	for (int tc = 1; tc <= testCase; tc++) {
		init();
		dfs(0,0);
		//printf("#%d %d\n", tc, ret);
		printf("%d\n", ret);
	}
	return 0;
}

이문제는 일단 조건을 잘 줘야한다고 생각한다. 위치에 맞게 인덱스를 바꿔야하는 부분이 있는데 그 부분을 명확히 잘 설정해줘야 한다. 처음 문제를 풀게 되면 자기만의 생각을 가지게 되어 그게 맞다고 착각하는 부분이 있습니다.

예를 들면 

1. 40을 넘어서 도착에 가는 부분을 40의 점수를 더한다던지 

2. 마지막에 말을 놓는 부분에 말이 있는데 그 말은 스킵하고 다른말을 진행 시킨다던지

3. 혹시나 순열을 뽑을때 벡터를 이용해 순열을 받는 다던지 

3가지를 주의 해야합니다.

 

1.의 경우는 사실 40을 넘어가서 멈추게 되는 경우 40만 안더하면되구

2.의 경우는 중복 위치인경우 새로 말의 순서를 받아서 실행 하고

3.의 경우 그냥 배열로 받으면됩니다. 3의 경우는 벡터로 받아 진행하면 시간 초과 걸릴꺼에요 

 

그럼 처음 부터 잘되는지 확인하고 넘어가는 습관을 가진 저같은 사람은 순열이 아닌가 생각 할 수 있습니다.

하지만 저는 여러가지 방법을 항상 적용해보기 때문에 이부부의 딜레마에 빠지지 않았지만 주의하세요

물론 순열로 안해도 되는 방법이 있을 수 있어요 하지만 순열로 한다면 주의 하는게 좋겠죠?