728x90
반응형
https://www.acmicpc.net/problem/17825
17825번: 주사위 윷놀이
주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다. 처음에는 시작 칸에 말 4개가 있다. 말은 게임판에 그려진 화살표의 방향대로만 이동할 수 있다. 말이 파란색 칸에서 이동을 시작하면
www.acmicpc.net
최종 코드
GitHub - hwayeon351/BEAKJOON-Algorithms: 백준 알고리즘 소스 코드 모음
백준 알고리즘 소스 코드 모음. Contribute to hwayeon351/BEAKJOON-Algorithms development by creating an account on GitHub.
github.com
//
// main.cpp
// BJ17825
//
// Created by 최화연 on 2022/04/28.
//
#include <iostream>
#include <string.h>
using namespace std;
struct Space {
int next[2] = {0, };
int score;
};
Space board[33] = {
//0~5
{{1, 0}, 0}, {{2, 0}, 2}, {{3, 0}, 4}, {{4, 0}, 6}, {{5, 0}, 8}, {{6, 21}, 10},
//6~10
{{7, 0}, 12}, {{8, 0}, 14}, {{9, 0}, 16}, {{10, 0}, 18}, {{11, 24}, 20},
//11~15
{{12, 0}, 22}, {{13, 0}, 24}, {{14, 0}, 26}, {{15, 0}, 28}, {{16, 27}, 30},
//16~20
{{17, 0}, 32}, {{18, 0}, 34}, {{19, 0}, 36}, {{20, 0}, 38}, {{32, 0}, 40},
//21~25
{{22, 0}, 13}, {{23, 0}, 16}, {{26, 0}, 19}, {{25, 0}, 22}, {{26, 0}, 24},
//26~30
{{30, 0}, 25}, {{28, 0}, 28}, {{29, 0}, 27}, {{26, 0}, 26}, {{31, 0}, 30},
//31, 32
{{20, 0}, 35}, {{0, 0}, 0}
};
int horse[5] = {0, };
int dice[10] = {0, };
int max_score = 0;
void play_game(int i, int score) {
if (score > max_score) max_score = score;
if (i >= 10) return;
for (int h=1; h<=4; h++) {
if (horse[h] >= 32) continue;
//파란길로 가야할 때
if (horse[h] == 5 || horse[h] == 10 || horse[h] == 15) {
int temp_horse = horse[h];
int new_horse = board[horse[h]].next[1];
for (int d=1; d<dice[i]; d++) {
new_horse = board[new_horse].next[0];
if (new_horse >= 32) break;
}
bool check = true;
for (int hh=1; hh<=4; hh++) {
if (h == hh) continue;
if (new_horse < 32 && new_horse == horse[hh]) {
check = false;
break;
}
}
if (check) {
horse[h] = new_horse;
int new_score = score;
if (new_horse < 32) new_score += board[new_horse].score;
play_game(i+1, new_score);
horse[h] = temp_horse;
}
}
//빨간길로 가야할 때
else {
int temp_horse = horse[h];
int new_horse = horse[h];
for (int d=0; d<dice[i]; d++) {
new_horse = board[new_horse].next[0];
if (new_horse >= 32) break;
}
bool check = true;
for (int hh=1; hh<=4; hh++) {
if (h == hh) continue;
if (new_horse < 32 && new_horse == horse[hh]) {
check = false;
break;
}
}
if (check) {
horse[h] = new_horse;
int new_score = score;
if (new_horse < 32) new_score += board[new_horse].score;
play_game(i+1, new_score);
horse[h] = temp_horse;
}
}
}
}
int main(int argc, const char * argv[]) {
for (int i=0; i<10; i++) {
cin >> dice[i];
}
play_game(0, 0);
cout << max_score << endl;
return 0;
}풀이 과정
풀이 시간 1시간 16분
#include <iostream>
#include <string.h>
using namespace std;
struct Space {
int next[2] = {0, };
int score;
};
Space board[33] = {
//0~5
{{1, 0}, 0}, {{2, 0}, 2}, {{3, 0}, 4}, {{4, 0}, 6}, {{5, 0}, 8}, {{6, 21}, 10},
//6~10
{{7, 0}, 12}, {{8, 0}, 14}, {{9, 0}, 16}, {{10, 0}, 18}, {{11, 24}, 20},
//11~15
{{12, 0}, 22}, {{13, 0}, 24}, {{14, 0}, 26}, {{15, 0}, 28}, {{16, 27}, 30},
//16~20
{{17, 0}, 32}, {{18, 0}, 34}, {{19, 0}, 36}, {{20, 0}, 38}, {{32, 0}, 40},
//21~25
{{22, 0}, 13}, {{23, 0}, 16}, {{26, 0}, 19}, {{25, 0}, 22}, {{26, 0}, 24},
//26~30
{{30, 0}, 25}, {{28, 0}, 28}, {{29, 0}, 27}, {{26, 0}, 26}, {{31, 0}, 30},
//31, 32
{{20, 0}, 35}, {{0, 0}, 0}
};
int horse[5] = {0, };
int dice[10] = {0, };
int max_score = 0;
void play_game(int i, int score) {
if (score > max_score) max_score = score;
if (i >= 10) return;
for (int h=1; h<=4; h++) {
if (horse[h] >= 32) continue;
//파란길로 가야할 때
if (horse[h] == 5 || horse[h] == 10 || horse[h] == 15) {
int temp_horse = horse[h];
int new_horse = board[horse[h]].next[1];
for (int d=1; d<dice[i]; d++) {
new_horse = board[new_horse].next[0];
if (new_horse >= 32) break;
}
bool check = true;
for (int hh=1; hh<=4; hh++) {
if (h == hh) continue;
if (new_horse < 32 && new_horse == horse[hh]) {
check = false;
break;
}
}
if (check) {
horse[h] = new_horse;
int new_score = score;
if (new_horse < 32) new_score += board[new_horse].score;
play_game(i+1, new_score);
horse[h] = temp_horse;
}
}
//빨간길로 가야할 때
else {
int temp_horse = horse[h];
int new_horse = horse[h];
for (int d=0; d<dice[i]; d++) {
new_horse = board[new_horse].next[0];
if (new_horse >= 32) break;
}
bool check = true;
for (int hh=1; hh<=4; hh++) {
if (h == hh) continue;
if (new_horse < 32 && new_horse == horse[hh]) {
check = false;
break;
}
}
if (check) {
horse[h] = new_horse;
int new_score = score;
if (new_horse < 32) new_score += board[new_horse].score;
play_game(i+1, new_score);
horse[h] = temp_horse;
}
}
}
}
int main(int argc, const char * argv[]) {
for (int i=0; i<10; i++) {
cin >> dice[i];
}
play_game(0, 0);
cout << max_score << endl;
return 0;
}이전 풀이
풀이 시간 2시간 24분
게임판을 표현하는 방법과 이동방향을 결정하는 방법을 생각하고 문제에 나와있는 로직을 제대로 구현하면 풀리는 문제이다.
나는 게임판 표현과 이동방향 결정을 다음과 같이 설계했다.
1. 게임판을 표현하는 방법
게임판에 칸이 시작점과 도착점을 포함하여 33개가 존재한다. 따라서 사이즈가 33인 1차원 배열인 map으로 표현할 것이다.
각 칸의 빨간색 번호가 해당 칸의 인덱스이며, 앞으로 이를 loc이라고 칭하겠다.
//map[loc] = loc 위치의 점수
//loc = 0 -> 출발지, loc = 32 -> 도착지
int map[33] = {0, 2, 4, 6, 8, 10,
12, 14, 16, 18, 20,
22, 24, 26, 28, 30,
32, 34, 36, 38, 13,
16, 19, 22, 24, 28,
27, 26, 25, 30, 35, 40, 0};
2. 이동 방향을 결정하는 방법
말이 턴의 주사위 값만큼 한 칸씩 이동할 것이기 때문에, 매 칸마다 어느 방향으로 갈지를 고려해야한다.
loc = 5, 10, 15에서만 이동방향이 2가지 존재하고, 나머지 loc에서는 계속 한 방향으로 나아가면 된다.
따라서 이동할 거리값을 나타내는 go 배열을 만들어 줄 것이다.
2차원 배열로 나타내어 1번째 인덱스 값은 loc, 2번째 인덱스 값은 이동방향 변경(1), 이동방향 변경 없음(0)으로 나타내주도록 하였다.
5
대부분의 loc은 map의 loc을 참고하면, go[loc] = {1, 0}으로 구성하면 된다. 즉, 이동 방향 변경이 없기 때문에 거리값 = 1 만큼 이동하면 해당 loc에서 다음 loc으로 이동할 수 있다.
하지만, 처리해줘야 하는 예외적인 loc이 있다.
(1) loc = 5, 10, 15일 때, 이동 방향 변경이 있을 수 있다.
- loc = 5의 경우
이동하는 도중에 도착한 경우에는 이동방향 변경이 일어나지 않는다.
즉, loc = 5 -> loc = 6으로 가면 되기 때문에 거리값 = 1(go[5][0] = 1)이다.
이전 턴에서 말이 loc = 5에서 이동을 마쳐서 다음 턴에서 loc = 5에서 이동을 시작하는 경우에는 이동방향을 변경해야 한다.
즉, loc = 5 -> loc = 20으로 가야하므로 거리값 = 5(go[5][1] = 5)이다.
- loc = 10의 경우
이동방향 변경이 일어나지 않는 경우, loc = 10 -> loc = 11로 가면 되기 때문에 거리값 = 1(go[10][0] = 1)이다.
이동방향을 변경해야 하는 경우, loc = 10 -> loc = 23으로 가야하므로 거리값 = 13(go[10][1] = 13)이다.
- loc = 15의 경우
이동방향 변경이 일어나지 않는 경우, loc = 15 -> loc = 16로 가면 되기 때문에 거리값 = 1(go[15][0] = 1)이다.
이동방향을 변경해야 하는 경우, loc = 15 -> loc = 25으로 가야하므로 거리값 = 10(go[15][1] = 10)이다.
(2) loc = 19, 22, 24일 때, 다음 칸으로 이동하는 거리 값이 다르다.
- loc = 19의 경우
loc = 19 -> loc = 31이므로, 거리값 = 12(go[19][0] = 12)이다.
- loc = 22의 경우
loc = 22 -> loc = 28이므로, 거리값 = 6(go[22][0] = 6)이다.
- loc = 24의 경우
loc = 24 -> loc = 28이므로, 거리값 = 4(go[24][0] = 4)이다.
이를 모두 반영하면 go 배열은 다음과 같다.
/*
1. go[loc][0] = loc 위치에서 방향 전환 없이 다음 위치로 가기 위한 거리값
loc = 0~18, 20, 21, 23, 25~31 -> 거리값 = 1
예외) loc = 19 -> 거리값 = 12, loc = 22 -> 거리값 = 6, loc = 24 -> 거리값 = 4
2. go[loc][1] = loc 위치에서 방향 전환이 이뤄질 때 다음 위치로 가기 위한 거리값
loc = 5 -> 거리값 = 15, loc = 10 -> 거리값 = 13, loc = 15 -> 거리값 = 10
loc = 0~4, 6~9, 11~14, 16~31 -> 방향 전환 없음(거리값 = 0)
*/
int go[32][2] = {
{1, 0}, {1, 0}, {1, 0}, {1, 0}, {1, 0}, {1, 15},
{1, 0}, {1, 0}, {1, 0}, {1, 0}, {1, 13},
{1, 0}, {1, 0}, {1, 0}, {1, 0}, {1, 10},
{1, 0}, {1, 0}, {1, 0}, {12, 0}, {1, 0},
{1, 0}, {6, 0}, {1, 0}, {4, 0}, {1, 0},
{1, 0}, {1, 0}, {1, 0}, {1, 0}, {1, 0}, {1, 0}
};
이를 활용하여 문제를 풀면 다음과 같다.
#include <iostream>
#include <string.h>
using namespace std;
//map[loc] = loc 위치의 점수
//loc = 0 -> 출발지, loc = 32 -> 도착지
int map[33] = {0, 2, 4, 6, 8, 10,
12, 14, 16, 18, 20,
22, 24, 26, 28, 30,
32, 34, 36, 38, 13,
16, 19, 22, 24, 28,
27, 26, 25, 30, 35, 40, 0};
/*
1. go[loc][0] = loc 위치에서 방향 전환 없이 다음 위치로 가기 위한 거리값
loc = 0~18, 20, 21, 23, 25~31 -> 거리값 = 1
예외) loc = 19 -> 거리값 = 12, loc = 22 -> 거리값 = 6, loc = 24 -> 거리값 = 4
2. go[loc][1] = loc 위치에서 방향 전환이 이뤄질 때 다음 위치로 가기 위한 거리값
loc = 5 -> 거리값 = 15, loc = 10 -> 거리값 = 13, loc = 15 -> 거리값 = 10
loc = 0~4, 6~9, 11~14, 16~31 -> 방향 전환 없음(거리값 = 0)
*/
int go[32][2] = {
{1, 0}, {1, 0}, {1, 0}, {1, 0}, {1, 0}, {1, 15},
{1, 0}, {1, 0}, {1, 0}, {1, 0}, {1, 13},
{1, 0}, {1, 0}, {1, 0}, {1, 0}, {1, 10},
{1, 0}, {1, 0}, {1, 0}, {12, 0}, {1, 0},
{1, 0}, {6, 0}, {1, 0}, {4, 0}, {1, 0},
{1, 0}, {1, 0}, {1, 0}, {1, 0}, {1, 0}, {1, 0}
};
//pieces[i] = i번째 말의 위치 loc
int pieces[4] = {0, 0, 0, 0};
//order[i] = i 턴에 움직일 말의 인덱스
int order[10] = {0, };
//turn[i] = i 턴의 주사위 값
int turn[10] = {0, };
int max_score = 0;
void play_game(){
//처음에 말은 모두 시작점에 위치하므로 pieces를 모두 0으로 초기화한다
memset(pieces, 0, sizeof(pieces));
int score = 0;
//10번의 턴을 진행한다
for(int i=0; i<10; i++){
//i번째 턴에 움직일 말
int piece = order[i];
//현재 말의 위치
int now_loc = pieces[piece];
//이미 말이 도착지에 있는 경우, 해당 게임은 무효이므로 게임을 종료한다
if(now_loc >= 32) return;
//움직여야하는 칸 수(주사위 값)
int now_turn = turn[i];
//이동한 칸
int new_loc = 0;
//주사위 값만큼 말을 이동시킨다
while(now_turn > 0){
//현재 loc을 기준으로 이동 방향을 정한다
switch(now_loc){
case 5:
case 10:
case 15:
//loc = 5, 10, 15에서 이동이 시작된다면, 이동방향을 바꾼다
if(now_turn == turn[i])
new_loc = now_loc + go[now_loc][1];
//이동하는 도중 loc = 5, 10, 15을 지나가는 경우, 이동방향을 바꾸지 않는다
else
new_loc = now_loc + go[now_loc][0];
break;
default:
new_loc = now_loc + go[now_loc][0];
break;
}
//한 칸 이동한 loc으로 말의 위치를 옮겨준다
pieces[piece] = new_loc;
now_loc = pieces[piece];
new_loc = 0;
now_turn--;
//이동 도중 도착지에 도착하면 더이상 이동하지 않는다
if(now_loc >= 32) break;
}
//해당 말이 도착지에 도착한 경우
if(now_loc >= 32){
pieces[piece] = 32;
now_loc = 32;
}
else{
//같은 위치의 말이 있는지 체크
for(int j=0; j<4; j++){
if(piece == j) continue;
//같은 위치에 다른 말이 이미 존재한다면, 해당 게임은 무효이므로 게임을 종료한다
if(pieces[j] == now_loc) return;
}
}
//해당 말이 이동을 마쳤으므로 해당 loc의 점수를 더한다
score += map[now_loc];
}
//해당 게임의 score가 최대값인 경우, max_score를 갱신한다
if(score > max_score) max_score = score;
}
void get_order(int cnt){
//10번의 턴에 움직일 말들을 모두 정한 경우, 게임을 진행하여 점수를 계산한다
if(cnt == 10){
play_game();
return;
}
//해당 턴에 움직일 말을 0~3 중 하나 고른다
for(int i=0; i<4; i++){
order[cnt] = i;
get_order(cnt+1);
order[cnt] = 0;
}
}
int main(int argc, const char * argv[]) {
for(int i=0; i<10; i++){
cin >> turn[i];
}
//말을 놓는 모든 경우의 수를 구하고 게임을 진행한다
get_order(0);
cout << max_score << endl;
return 0;
}
//시간복잡도 = O(N), 공간복잡도 = O(N)
//10번의 턴에 어떤 말을 옮길지 결정하는 중복 순열 -> 4^10, 10번의 턴의 주사위 값이 5인 경우 -> 10*5
//따라서 최악의 경우, 4^10*5*10 = 5천만번의 연산이 이뤄진다.
728x90
반응형
'코테 노트 > 백준' 카테고리의 다른 글
| 백준 12015 가장 긴 증가하는 부분 수열 2 Python 3 (0) | 2021.10.08 |
|---|---|
| 백준 14002 가장 긴 증가하는 부분 수열 4 Python 3 (0) | 2021.10.06 |
| 백준 7453 합이 0인 네 정수 Python 3 (0) | 2021.10.05 |
| 백준 17837 새로운 게임 2 C++ (0) | 2021.10.05 |
| 백준 17143 낚시왕 C++ (0) | 2021.10.05 |