이번에는 백준 17825번 주사위 윷놀이 문제를 풀어보았습니다.
이 문제는 게임판 자체가 일반적인 일직선 구조가 아니라, 특정 위치에서 파란색 경로로 분기되는 구조를 가지고 있습니다.
그래서 먼저 게임판을 그래프 형태로 직접 구현한 뒤, 10번의 턴마다 4개의 말 중 하나를 선택하는 모든 경우를 DFS로 탐색하였습니다.
각 재귀 호출이 끝난 뒤에는 말의 위치와 점수를 원래 상태로 복구하여 다른 경우의 수도 확인하도록 구현하였습니다.
문제 설명
게임판에는 총 4개의 말이 있고, 처음에는 모두 시작 칸에 있습니다.
총 10번의 턴이 진행되며, 각 턴마다 미리 주어진 주사위 값을 이용하여 말 하나를 이동시켜야 합니다.
말이 파란색 칸에서 출발하면 파란색 경로를 따라가고, 그렇지 않다면 일반 경로를 따라갑니다.
또한 이동을 마친 위치에 다른 말이 있다면 해당 말은 이동시킬 수 없습니다.
10번의 이동을 모두 수행했을 때 얻을 수 있는 점수의 최댓값을 구하는 문제입니다.
풀이 아이디어
먼저 게임판을 그래프로 구현하였습니다.
각 칸을 하나의 인덱스로 나타내고,
int int_map[33]에는 해당 칸의 점수를 저장하였습니다.
그리고
vector<vector<int>> link를 이용하여 각 칸에서 다음으로 이동할 수 있는 칸을 연결하였습니다.
일반 칸에서는 다음 칸 하나만 존재하지만,
10, 20, 30점에 해당하는 파란색 분기 칸에서는 일반 경로와 파란색 경로 두 개를 연결하였습니다.
이후 DFS를 이용하여 매 턴마다 4개의 말 중 이동 가능한 말을 모두 선택해보았습니다.
말을 하나 이동시킨 뒤 다음 턴으로 넘어가고, 재귀 호출이 끝나면 해당 말의 위치와 누적 점수를 복구하는 방식으로 백트래킹하였습니다.
코드
#include <bits/stdc++.h>
using namespace std;
struct horse{
int index = 0;
int sum = 0;
};
int dice_turn[10];
horse ret[4];
int max_val = INT_MIN;
int int_map[33] = {
0,2,4,6,8,10,
12,14,16,18,20,
13,16,19,
22,24,
22,24,26,28,30,
28,27,26,25,
30,35,
32,34,36,38,40,
0
};
vector<vector<int>> link(33, vector<int>());
void initialization() {
for (int i=0; i<5; i++) {
link[i].push_back(i+1);
}
link[5].push_back(6);
link[5].push_back(11);
for (int i=6; i<10; i++) {
link[i].push_back(i+1);
}
link[11].push_back(12);
link[12].push_back(13);
link[13].push_back(24);
link[10].push_back(16);
link[14].push_back(15);
link[15].push_back(24);
link[10].push_back(14);
for (int i=16; i<20; i++) {
link[i].push_back(i+1);
}
for (int i=21; i<24; i++) {
link[i].push_back(i+1);
}
link[24].push_back(25);
link[25].push_back(26);
link[26].push_back(31);
link[20].push_back(27);
link[20].push_back(21);
for (int i=27; i<=31; i++) {
link[i].push_back(i+1);
}
}
bool can_go(int horse_index, int cnt) {
int st = ret[horse_index].index;
int curr = st;
if (st == 5 || st == 10 || st == 20) {
curr = link[curr][1];
for (int i=1; i<cnt; i++) {
if (curr == 32) break;
curr = link[curr][0];
}
} else if (st == 32) {
return false;
} else {
for (int i=0; i<cnt; i++) {
if (curr == 32) break;
curr = link[curr][0];
}
}
for (int i=0; i<4; i++) {
if (curr != 32 && ret[i].index == curr) {
return false;
}
}
return true;
}
void go(int horse_index, int cnt) {
int st = ret[horse_index].index;
int curr = st;
if (st == 5 || st == 10 || st == 20) {
curr = link[curr][1];
for (int i=1; i<cnt; i++) {
if (curr == 32) break;
curr = link[curr][0];
}
} else {
for (int i=0; i<cnt; i++) {
if (curr == 32) break;
curr = link[curr][0];
}
}
ret[horse_index].index = curr;
ret[horse_index].sum += int_map[curr];
}
void solve(int horse_index, int turn) {
int curr_index = ret[horse_index].index;
int curr_sum = ret[horse_index].sum;
go(horse_index, dice_turn[turn]);
if (turn == 9) {
int sum = 0;
for (int i=0; i<4; i++) {
sum += ret[i].sum;
}
max_val = max(max_val, sum);
ret[horse_index].index = curr_index;
ret[horse_index].sum = curr_sum;
return;
}
for (int i=0; i<4; i++) {
if (!can_go(i,dice_turn[turn+1])) continue;
solve(i, turn+1);
}
ret[horse_index].index = curr_index;
ret[horse_index].sum = curr_sum;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
for (int i=0; i<10; i++)
cin >> dice_turn[i];
initialization();
solve(0,0);
cout << max_val;
return 0;
}풀이 흐름
-
게임판의 각 칸을 인덱스로 나누고 점수를
int_map에 저장합니다. -
각 칸에서 이동할 수 있는 다음 칸을
link에 저장하여 게임판을 그래프로 구현합니다. -
주사위 10개의 값을 입력받습니다.
-
현재 턴에서 이동할 말을 선택합니다.
-
can_go()를 통해 해당 말이 이동 가능한지 확인합니다. -
이동 가능하다면
go()를 이용해 실제 말을 이동시키고 점수를 추가합니다. -
다음 턴에서 다시 4개의 말 중 하나를 선택합니다.
-
마지막 턴까지 진행했다면 4개 말의 점수를 모두 더해 최댓값을 갱신합니다.
-
재귀 호출이 끝나면 이동시킨 말의 위치와 점수를 원래 상태로 복구합니다.
-
모든 경우를 확인한 뒤 최대 점수를 출력합니다.
구현 포인트
1. 말의 상태 저장
struct horse{
int index = 0;
int sum = 0;
};각 말마다 두 가지 정보를 저장하였습니다.
index: 현재 위치한 게임판의 인덱스sum: 현재까지 해당 말이 얻은 점수
4개의 말은 다음 배열로 관리하였습니다.
horse ret[4];처음에는 모두 시작 칸인 0번 인덱스에 있으며 점수도 0입니다.
2. 게임판을 인덱스로 표현
int int_map[33] = {
0,2,4,6,8,10,
12,14,16,18,20,
13,16,19,
22,24,
22,24,26,28,30,
28,27,26,25,
30,35,
32,34,36,38,40,
0
};게임판의 각 칸을 0번부터 32번까지의 인덱스로 표현하였습니다.
0번은 시작 칸이고, 32번은 도착 칸입니다.
따라서 시작과 도착의 점수는 0으로 설정하였습니다.
각 분기 경로에 존재하는 숫자들도 별도의 인덱스로 만들어 하나의 배열에 저장하였습니다.
3. 게임판을 인접 리스트로 구현
vector<vector<int>> link(33, vector<int>());각 칸에서 다음으로 이동 가능한 칸을 저장합니다.
일반적인 칸에서는 다음 칸 하나만 존재합니다.
예를 들어
for (int i=0; i<5; i++) {
link[i].push_back(i+1);
}와 같이 연결하였습니다.
즉,
0 → 1 → 2 → 3 → 4 → 5형태로 이동합니다.
4. 파란색 분기 처리
10점 칸에서는 일반 경로와 파란색 경로가 나뉩니다.
link[5].push_back(6);
link[5].push_back(11);따라서 link[5]에는 두 개의 다음 위치가 존재합니다.
link[5][0] : 일반 경로
link[5][1] : 파란색 경로20점과 30점에 해당하는 분기점도 같은 방식으로 구현하였습니다.
link[10].push_back(16);
link[10].push_back(14);link[20].push_back(27);
link[20].push_back(21);5. 파란색 칸에서 출발하는 경우
문제에서는 파란색 칸에서 이동을 시작할 때만 파란색 화살표를 따라가야 합니다.
따라서 현재 위치가 분기점인 경우를 따로 처리하였습니다.
if (st == 5 || st == 10 || st == 20) {
curr = link[curr][1];첫 번째 이동은 파란색 경로인 link[curr][1]을 사용합니다.
이후 이동은 다시 일반적인 다음 경로를 따라갑니다.
for (int i=1; i<cnt; i++) {
if (curr == 32) break;
curr = link[curr][0];
}중간에 파란색 칸을 지나더라도 이동 도중에는 파란색 화살표를 사용하지 않는 문제의 조건을 그대로 구현하였습니다.
6. 일반 위치에서 이동
분기점이 아닌 곳에서는 단순히 다음 칸을 cnt번 따라갑니다.
for (int i=0; i<cnt; i++) {
if (curr == 32) break;
curr = link[curr][0];
}도착 칸인 32번에 도달하면 주사위 수가 남아 있어도 이동을 종료합니다.
if (curr == 32) break;7. 도착한 말은 다시 선택할 수 없음
else if (st == 32) {
return false;
}이미 도착 칸에 있는 말은 다시 움직일 수 없습니다.
따라서 can_go()에서 현재 말의 위치가 32번이면 바로 false를 반환합니다.
8. 다른 말과 같은 위치인지 확인
말이 이동을 마친 위치에 다른 말이 존재하면 해당 말은 이동시킬 수 없습니다.
for (int i=0; i<4; i++) {
if (curr != 32 && ret[i].index == curr) {
return false;
}
}단, 도착 칸은 여러 말이 함께 존재할 수 있으므로
curr != 32조건을 추가하였습니다.
도착 칸이 아닌 경우에만 다른 말과 위치가 겹치는지 검사합니다.
9. can_go()와 go() 분리
bool can_go(int horse_index, int cnt)는 실제 상태를 변경하지 않고 해당 말을 이동시킬 수 있는지만 확인합니다.
반면
void go(int horse_index, int cnt)는 실제로 말을 이동시킵니다.
두 함수 모두 같은 방식으로 다음 위치를 계산하지만, go()에서는 마지막에 말의 상태를 변경합니다.
ret[horse_index].index = curr;
ret[horse_index].sum += int_map[curr];도착한 칸의 점수를 해당 말의 누적 점수에 추가합니다.
10. DFS로 모든 말 선택 경우 확인
for (int i=0; i<4; i++) {
if (!can_go(i,dice_turn[turn+1])) continue;
solve(i, turn+1);
}다음 턴에서 4개의 말 모두를 이동 후보로 확인합니다.
이동할 수 없는 말은 건너뛰고, 이동할 수 있는 말에 대해서만 재귀 호출합니다.
따라서 각 턴마다 가능한 모든 말 선택을 확인하게 됩니다.
11. 최대 경우의 수
각 턴마다 선택할 수 있는 말은 최대 4개입니다.
10개의 턴이 있으므로 단순하게 계산하면 최대 경우의 수는 다음과 같습니다.
4¹⁰ = 1,048,576실제로는 이미 도착했거나 다른 말과 충돌하여 선택할 수 없는 경우가 있기 때문에 탐색되는 경우의 수는 이보다 적습니다.
따라서 완전탐색으로 충분히 해결할 수 있습니다.
12. 상태 복구
현재 말을 이동시키기 전에 기존 상태를 저장합니다.
int curr_index = ret[horse_index].index;
int curr_sum = ret[horse_index].sum;이후 해당 말을 실제로 이동시킵니다.
go(horse_index, dice_turn[turn]);하위 재귀 탐색이 끝난 뒤에는 원래 상태로 되돌립니다.
ret[horse_index].index = curr_index;
ret[horse_index].sum = curr_sum;이렇게 해야 다른 말을 선택하는 경우를 동일한 이전 상태에서 탐색할 수 있습니다.
따라서 이 부분은 DFS에서 상태를 되돌리는 백트래킹에 해당합니다.
13. 마지막 턴 처리
if (turn == 9)주사위는 총 10개이고 인덱스는 0부터 시작하므로 turn == 9가 마지막 턴입니다.
마지막 말을 이동시킨 뒤 4개의 말이 얻은 점수를 모두 합합니다.
int sum = 0;
for (int i=0; i<4; i++) {
sum += ret[i].sum;
}현재까지의 최댓값과 비교하여 갱신합니다.
max_val = max(max_val, sum);이후 현재 말을 다시 원래 상태로 복구하고 재귀 호출을 종료합니다.
14. DFS와 백트래킹
이 문제에서는 매 턴마다 어떤 말을 선택할지 모든 경우를 탐색합니다.
따라서 기본적으로 DFS를 이용한 완전탐색입니다.
또한 특정 말을 이동한 뒤 하위 경우를 모두 확인하면
ret[horse_index].index = curr_index;
ret[horse_index].sum = curr_sum;을 통해 기존 상태로 돌아갑니다.
따라서 이 풀이는 게임판 시뮬레이션 + DFS 완전탐색 + 백트래킹 방식이라고 볼 수 있습니다.
시간복잡도
각 턴마다 최대 4개의 말을 선택할 수 있고 총 10턴이므로 최대 탐색 경우는
4¹⁰개입니다.
각 상태에서 말의 이동은 주사위 값이 최대 5이므로 상수 시간에 가깝고, 다른 말과의 충돌 확인도 4개만 확인합니다.
따라서 전체 시간복잡도는 대략
O(4¹⁰)으로 볼 수 있습니다.
약 100만 개 정도의 경우이므로 충분히 해결할 수 있습니다.
