-
백준 17825번 주사위 윷놀이PS 2020. 3. 9. 00:32
https://www.acmicpc.net/problem/17825
17825번: 주사위 윷놀이
주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다. 가장 처음에는 시작에 말 4개가 있다. 말은 게임판에 적힌 화살표의 방향대로만 이동할 수 있다. 파란색 칸에서 말이 이동을 시작하는 경우에는 파란색 화살표의 방향으로 이동해야 하며 파란색 칸을 지나가는 경우에는 빨간 화살표의 방향대로 이동해야 한다. 게임은 1부터 5까지 한 면에 하나씩 적혀있는 5면 주사위를 굴려서 나온 수만큼 이동하는 방식으로 진행한다. 이동하려고 하는 칸에 말이 이미 있는 경우에
www.acmicpc.net
<접근방법>
완전 탐색 문제입니다.
백트래킹으로 순열을 구현하여 시뮬레이션 하면 됩니다.
윷놀이판의 저장 방법이나 윷놀이판의 순회 방법을 결정하는 것이 핵심이었다고 생각합니다.
저는 파란색 칸이 5로 나누어 떨어지는 점을 이용하여 구현하였습니다.
다른 분의 코드를 참고해보니 그냥 일차원 배열에 모두 저장하고 인덱스 혹은 방향을 조절해주는 것이
훨씬 쉬워보입니다.
<느낀 점>
<코드>
#include <iostream> #include <algorithm> using namespace std; struct point { int y, x; bool suc; }; int s[10], a[10]; int map[7][22]; int res; void map_set() { int tmp2[8] = {10, 13, 16, 19, 25}; int tmp4[7] = {20, 22, 24, 25}; int tmp5[4] = {25, 30, 35, 40}; int tmp6[8] = {30, 28, 27, 26, 25}; map[0][0] = 0; for (int j = 1; j < 21; j++) { map[0][j] = map[0][j - 1] + 2; } int j = 0; for (int i = 0; i < 21; i++) { if (i < 16) { map[2][i] = 0; } else { map[2][i] = tmp2[j++]; } } j = 0; for (int i = 0; i < 21; i++) { if (i < 17) { map[4][i] = 0; } else { map[4][i] = tmp4[j++]; } } j = 0; for (int i = 0; i < 21; i++) { if (i < 17) { map[5][i] = 0; } else { map[5][i] = tmp5[j++]; } } j = 0; for (int i = 0; i < 21; i++) { if (i < 16) { map[6][i] = 0; } else { map[6][i] = tmp6[j++]; } } } int simul() { bool visit[7][22] = {false, }; int sum = 0; point h[4]; for (int i = 0; i < 4; i++) { h[i].y = 0; h[i].x = 0; h[i].suc = false; } for (int z = 0; z < 10; z++) { int y = h[s[z]].y; int x = h[s[z]].x; int move = a[z]; if (h[s[z]].suc) continue; visit[y][x] = false; if (map[y][x] == 40) { visit[0][x] = false; visit[5][x] = false; } if (map[y][x] % 5 == 0 && y == 0 && x != 0) { y = map[y][x] / 5; if (y == 2) { x = 16; } else if (y == 4) { x = 17; } else if (y == 6) { x = 16; } } while (move--) { x++; if (map[y][x] == 25) { y = map[y][x] / 5; x = 17; } if (x >= 21) { h[s[z]].suc = true; break; } } if (!h[s[z]].suc) { if (visit[y][x]) return 0; sum += map[y][x]; visit[y][x] = true; if (map[y][x] == 40) { visit[0][x] = true; visit[5][x] = true; } h[s[z]].y = y; h[s[z]].x = x; } } return sum; } void dfs(int dep) { if (dep == 10) { res = max(res, simul()); return; } for (int i = 0; i < 4; i++) { s[dep] = i; dfs(dep + 1); } } int main() { for (int i = 0; i < 10; i++) { cin >> a[i]; } map_set(); dfs(0); cout << res << '\n'; return 0; }
반응형'PS' 카테고리의 다른 글
백준 12851번 숨바꼭질2 (0) 2020.03.10 백준 1697번 숨바꼭질 (0) 2020.03.10 백준 16932번 모양 만들기 (1) 2020.03.07 백준 16953번 A->B (0) 2020.03.07 백준 2151번 거울 설치 (0) 2020.03.07