17825번: 주사위 윷놀이
첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다.
www.acmicpc.net
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;
}'알고리즘 문제풀이 > 구현' 카테고리의 다른 글
| 백준 17143 [C++] (0) | 2021.03.08 |
|---|---|
| 백준 17822 [C++] (0) | 2021.03.08 |
| 백준 17837 [C++] (0) | 2021.03.06 |
| 백준 16235 [C++] (0) | 2021.03.06 |
| 백준 17779 [C++] (0) | 2021.03.05 |
