백준 17825 [C++]

www.acmicpc.net/problem/17825

17825번: 주사위 윷놀이

1. 풀이방법

- 쉽다고 생각하면서 , 시작해서 개고생하며 어렵게 끝낸 문제입니다.....

 

- 첫번째 문제점, 30 노드가 중복되는 것을 체크하지 못한점.

 

- 30 노드에 도착하면 방향을 바꾸도록 설정했다가 다른 30 (끝 쪽에 가까운) 거기에 말들이 도착헀을때도 방향을 바꾸는 현상 발생.

 

- 두번째 문제점, 방문체크를 할때 여러개 있는 노드들을 고려하지 않은 것.

 

- 문제를 보면, 두개이상 존재하는 노드들이 있다 (16, 22,28,30.....)

 

- 결국 현재 말들의 위치만을 비교함으로써 겹쳐지는지 아닌지 알 수 가 없다.

 

- 결국 코드를 싹 지우고, 다시 짜면서 해결한 방법은

 

- 각각 고유의 번호를 가지는 노드들로 같은 모양의 그래프를 만들어 준 후, 문제에서의 노드들은 점수들로서

 

- 매칭을 시켜주었습니다. 그러면 첫, 두 번째 문제점들이 모두 해결됩니다.

 

- 그림을 보시면 아이디어를 이해하시기 편할 겁니다.

 

- 전체적인 문제해결은 dfs를 이용한 완전탐색 입니다.

 

 

 

2. 주의사항

- 일단 코드를 작성하기 전, 문제를 항상 정확히 파악하고 시작하고자 노력하지만

 

- 이 문제처럼, 처음 시작할 때 발생하는 문제를 예상하지 못하고 시작하면 굉장히 어려워 지고 꼬입니다....

 

- 역시, 주의사항은...... 문제를 꼼꼼히 잘 분석하자......

 

 

3. 나의코드

#include<bits/stdc++.h>
using namespace std;

// 시작노드 0, 도착점 노드 21
int route[4][33];
int score[33]; // 점수계산을 위한 노드
int maxresult;
int inputnum[10];
pair<int, int> ob[4]; //4개의말 (현재위치, 타고있는 방향)

void inputs() {
	for (int i = 0; i < 10; i++) {
		cin >> inputnum[i];
	}
}
void setscore() {
	for (int i = 1; i <= 20; i++) {
		score[i] = 2 * i;
	}
	score[22] = 13; score[23] = 16; score[24] = 19;
	score[25] = 25; score[30] = 26; score[29] = 27;
	score[28] = 28; score[26] = 22; score[27] = 24;
	score[31] = 30; score[32] = 35; score[21] = 0;
}
void makegraph() {
	for (int i = 0; i < 21; i++) {
		route[0][i] = i + 1;
	}
	route[0][21] = 21;
	route[1][5] = 22; route[1][22] = 23; route[1][23] = 24;
	route[1][24] = 25; route[1][25] = 31; route[1][31] = 32;
	route[1][32] = 20; route[1][20] = 21; route[1][21] = 21;
	route[2][10] = 26; route[2][26] = 27; route[2][27] = 25;
	route[2][25] = 31; route[2][31] = 32; route[2][32] = 20;
	route[2][20] = 21; route[2][21] = 21;
	route[3][15] = 28; route[3][28] = 29; route[3][29] = 30;
	route[3][30] = 25; route[3][25] = 31; route[3][31] = 32;
	route[3][32] = 20; route[3][20] = 21; route[3][21] = 21;
}
bool existcheck(int s,int index) {
	if (s == 21) return false;
	for (int i = 0; i < 4; i++) {
		if (i == index) continue;
		if (ob[i].first == 21) continue;
		if (ob[i].first == s) return true;
	}
	return false;
}
void makecase(int cnt,int resultsum) {
	if (cnt == 10) {
		maxresult = max(resultsum, maxresult);
		return;
	}
	int thisnum = inputnum[cnt];
	for (int i = 0; i < 4; i++) {
		if (ob[i].first == 21) continue; //이미 도착점에 있는 말
		int prevnum = ob[i].first;
		int prevdir = ob[i].second;
		for (int j = 0; j < thisnum; j++) {
			ob[i].first = route[prevdir][ob[i].first];
		}
		if (ob[i].first == 5) ob[i].second = 1;
		if (ob[i].first == 10) ob[i].second = 2;
		if (ob[i].first == 15) ob[i].second = 3;

		if (!existcheck(ob[i].first,i)) {
			makecase(cnt + 1, resultsum + score[ob[i].first]);
		}
		ob[i].first = prevnum;
		ob[i].second = prevdir;

	}
}
int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	inputs();
	setscore();
	makegraph();
	makecase(0,0);
	cout << maxresult;
	return 0;
}