C++/삼성SW기출
[백준 17825: 주사위 윷놀이] (C++)
snowman95
2019. 10. 26. 00:29
728x90
반응형
삼성 SW 역량 테스트
https://www.acmicpc.net/workbook/view/1152
ㄴ주사위 윷놀이
https://www.acmicpc.net/problem/17825
l 문제
| 1. 주사위를 굴려서 나온 수 만큼 말을 이동시키는 윷놀이 게임이다. 일반적인 윷놀이 게임과 규칙은 동일하지만 첫 번째 코너를 밟고나서 중앙을 밟지 않아도 무조건 도착 지점으로 꺾는다. ( 원래 윷놀이는 중앙을 밟지 않으면 그대로 직진 ) |
| 2. 말 처음 시작 지점에 말 4개가 있다. 말은 순서와 상관 없이 아무 말이나 이동시킬 수 있고 이동하려는 칸에 이미 말이 있으면 이동할 수 없다. ( 시작, 도착 칸 제외 ) 도착 지점 넘어가면 도착 지점에서 이동을 마치며, 도착한 말은 더 이상 이동할 수 없다. 말이 이동을 마칠때마다 칸에 적혀있는 수가 점수에 추가된다. |
| 3. 주사위 5면 주사위의 각 면에 1 ~ 5 까지의 수가 적혀있다 주사위를 굴려서 나온 수 만큼 말을 이동시킬 수 있다. 주사위에서 나올 수 10개가 순서대로 입력으로 주어짐 |
l 입력
| 첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다. |
l 출력
| 얻을 수 있는 점수의 최댓값을 출력한다. |
l 주의
이 문제는 평범한 윷놀이가 아닙니다.
원래 윷놀이는 코너( 10 )을 밟으면 지름길로 가서 중앙( 25 )를 밟아야 도착 지점으로 꺾을 수 있는데
이 문제는 중앙을 밟지 않아도 무조건 도착 지점으로 꺾어야 합니다.
이 윷놀이는 도착 지점까지 4가지 경로가 있습니다.
l 풀이
| DFS로 이동시킬 말을 선택하고 시뮬레이션 |
| 말 이동 함수 { 1. 코너에 진입한 경우 2. 가로 통로 - 오른쪽 방향 3. 가로 통로 - 왼쪽 방향 4. 도착지점 넘어간 경우 그외에 일반적인 경우 } DFS 함수 { 1. 말 4개를 차례대로 진행 2. 말 이동 함수 3. 이동한 위치에 다른 말이 존재하면 넘어감 4. DFS 함수( 다음 턴 ) } |
| 윷놀이 판 |
| 일반적인 경로, 코너 3개, 가로 통로, 세로 통로, 중앙 이렇게 분리하여 생각하였습니다. 코너를 밟게 되면 통로로 들어가게 되고 세로 통로는 그대로 직진하고 가로 통로는 ( 말 위치 + 주사위 수 )가 통로 길이를 넘어가면 도착 지점 쪽으로 꺾어서 진행하도록 하였습니다.  |
| 통로 번호 |
| 통로 번호를 어떻게 지정할지 참 애먹었는데 일반 경로 1 ~ 20, 도착이 21 가로 통로( R ) 26, 27, 28 가로 통로( L ) 45, 46, 47 세로 통로 34, 35, 36, 37, 38, 39 ( 39은 20으로 취급 ) 이렇게 지정한 이유는 주사위 수가 최대 5이기 때문에 20 + 5 = 25 보다 큰 26부터 ~ 28 28 + 5 = 33 보다 큰 34 부터 ~ 39 39 + 5 = 44 보다 큰 45 부터 ~ 47 뭐 이런 식으로 통로 번호를 지정해주었습니다. 사실 경로 4개 다 따로 범위 정해주고 각각 배열에 다 때려넣어서 해도 될 것 같습니다. |
l 코드
#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
const int TURNEL_GOAL = 44, GOAL = 21;
enum turnel
{
center = 40,
rs = 26, re = 28,
ls = 50, le = 52,
};
unordered_map<int, int> corner = {
{5, 26}, {10, 38}, {15, 50}
};
unordered_map<int, int> board_score = {
{26, 13}, {27, 16}, {28, 19},
{50, 28}, {51, 27}, {52, 26},
{38, 22}, {39, 24}, {40, 25}, {41, 30}, {42, 35}, {43, 40}
};
int ans, dice[10], h[4], score[4];
bool visited[53];
int gain_score(int p)
{
if (p < GOAL) return p * 2;
if (p == GOAL) return 0;
return board_score[p];
}
int move(int start, int cnt)
{
int next = start + cnt;
// 코너에 진입한 경우
if (start == 5 || start == 10 || start == 15)
next = move(corner[start], cnt - 1);
// 오른 통로
else if (turnel::rs <= start && start <= turnel::re)
{
if (next > turnel::re) next = turnel::center + next - turnel::re - 1;
}
// 왼 통로
else if (turnel::ls <= start && start <= turnel::le)
{
if (next > turnel::le) next = turnel::center + next - turnel::le - 1;
}
// 종료 지점
if ((GOAL <= next && next <= GOAL + 4) || (TURNEL_GOAL <= next && next <= TURNEL_GOAL + 4))
next = GOAL;
else if (next == TURNEL_GOAL - 1)
next = GOAL-1;
return next;
}
void dfs(int n)
{
if (n == 10)
{
ans = max(ans, score[0] + score[1] + score[2] + score[3]);
return;
}
register int i, next, s, pos;
// 1. 말 4개를 차례대로 진행
for (i = 0; i < 4; ++i)
{
// 완주한 것이 아니면 이동 가능
if (h[i] != GOAL)
{
// 2. 이동
next = move(h[i], dice[n]);
// 3. 이동한 위치에 다른 말이 존재
if (next != GOAL && visited[next])
continue;
pos = h[i];
visited[pos] = false;
visited[next] = true;
h[i] = next;
s = gain_score(next);
score[i] += s;
dfs(n + 1);
visited[pos] = true;
visited[next] = false;
h[i] = pos;
score[i] -= s;
}
}
}
int main()
{
// freopen("input.txt", "r", stdin);
ios_base::sync_with_stdio(0); cin.tie(0);
register int i;
for (i = 0; i < 10; ++i)
cin >> dice[i];
dfs(0);
cout << ans;
return 0;
}
통로 이동 부분 때문에 코드가 좀 더럽습니다 ㅠㅠ
끔찍한 하드 코딩이군요
반응형