문제
주사위 윷놀이는 다음과 같은 게임판에서 하는 게임이다.
가장 처음에는 시작에 말 4개가 있다. 말은 게임판에 적힌 화살표의 방향대로만 이동할 수 있다. 파란색 칸에서 말이 이동을 시작하는 경우에는 파란색 화살표의 방향으로 이동해야 하며 파란색 칸을 지나가는 경우에는 빨간 화살표의 방향대로 이동해야 한다.
게임은 1부터 5까지 한 면에 하나씩 적혀있는 5면 주사위를 굴려서 나온 수만큼 이동하는 방식으로 진행한다. 이동하려고 하는 칸에 말이 이미 있는 경우에는 그 칸으로 이동할 수 없다. 시작과 도착칸은 말이 이미 있어도 이동할 수 있다. 말이 이동을 마칠때마다 칸에 적혀있는 수가 점수에 추가된다.
말이 도착으로 이미 이동한 경우에는 더 이상 이동할 수 없고, 말이 이동하려고 하는 칸이 도착을 넘어가는 경우에는 도착에서 이동을 마친다.
주사위에서 나올 수 10개를 미리 알고있을때, 얻을 수 있는 점수의 최댓값을 구해보자.
입력
첫째 줄에 주사위에서 나올 수 10개가 순서대로 주어진다.
출력
얻을 수 있는 점수의 최댓값을 출력한다.
진짜 어려운 문제였음.
각 칸마다 인덱스를 지정해서 어떨때는 어떻게 넘어가라 어떨때는 어떻게 이동해라 하나하나
조건으로 처리해 주는 것은 미친짓이다.
우선 말이 이동할 수 있는 경로를 분석하는게 핵심.
1. 일반적인 경로
2. 10을 밟았을 때 오른쪽으로 꺾이는 경로
3. 20을 밟았을 때 아래로 내려가는 경로
4. 30을 밟았을 때 왼쪽으로 꺾이는 경로
그리고 각 말에게는 자신이 지금 어떤 루트로 가고있는지와 그 루트에서 몇번째 인덱스에 위치하는지
그리고 도착여부의 정보가 포함된다.
말이 이동하는 것은 for문으로 각 말을 돌면서 DFS로 진행하고 10번째 주사위까지 처리하고 나서는 최대값 갱신을 해줌.
말은 최초 경로 시작 위치에서 모두 시작하고, 주사위만큼 location을 증가 시키면서 최초 경로일 때, 10인지 15인지 20인에 따라 경로가 바뀔지 안바뀔지를 결정해 준다.
자신의 현재 경로에서 주사위 수만큼에 따라 목표 위치를 정해주고 해당 위치에 말이 있는지 조사, 혹은 도착 지점이상으로 벗어나는지 조사 후에 둘다 아닌 경우는 점수를 더해주는 작업을 해주고 백트래킹 으로 DFS 호출을 해준다.
둘중에 하나라도 해당한다면 다음번 말로 넘어가준다
말이 존재하는지 여부는 자신의 목표 지점의 루트 정보와 loc 정보가 어떤 말과 일치하는 경우도 해당되지만 ,
다른 경로인 경우에도 공통적으로 겹치는 path에 대해서 조사를 해주어야 한다.
25,30,35,40 에 대한 조사를 해주고 여기에서 만나게 되는 경우도 이동하지 않아야 한다.
#include<iostream>
using namespace std;
int map[4][22] = {
{0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38,40,0},
{10,13,16,19,25,30,35,40,0},
{20,22,24,25,30,35,40,0},
{30,28,27,26,25,30,35,40,0}
};
bool visit[4][22];
int maplen[4] = { 21,8,7,8 };
struct Node{
int road;
int loc;
bool arrived;
};
Node horse[4];
int dice[10];
int maxa = -1;
int result;
bool check(int road,int loc,int idx)
{
for(int i = 0; i < 4; i++)
{
if( !horse[i].arrived && map[horse[i].road][horse[i].loc] != 0)
{
if(horse[i].road == road && horse[i].loc == loc)
{
return false;
}
else if(map[horse[i].road][horse[i].loc] == 25 && map[road][loc] == 25)
{
return false;
}
else if(map[horse[i].road][horse[i].loc] == 30 && map[road][loc] == 30)
{
if(map[horse[i].road][horse[i].loc-1] == 25 && map[road][loc-1] == 25)
{
return false;
}
}
else if(map[horse[i].road][horse[i].loc] == 35 && map[road][loc] == 35)
{
return false;
}
else if(map[horse[i].road][horse[i].loc] == 40 && map[road][loc] == 40)
{
return false;
}
}
}
return true;
}
void DFS(int cur)
{
if(cur == 10)
{
if(result > maxa)
{
maxa = result;
}
return;
}
for(int i = 0; i < 4; i++)
{
int newloc = horse[i].loc + dice[cur];
int temploc = horse[i].loc;
int temproad = horse[i].road;
if( !horse[i].arrived)
{
if(horse[i].road == 0)
{
if(newloc == 5)
{
if(check(1,0,i))
{
horse[i].loc = 0;
horse[i].road = 1;
result += map[horse[i].road][horse[i].loc];
DFS(cur+1);
result -= map[horse[i].road][horse[i].loc];
horse[i].loc = temploc;
horse[i].road = temproad;
}
}
else if(newloc == 10)
{
if(check(2,0,i))
{
horse[i].loc = 0;
horse[i].road = 2;
result += map[horse[i].road][horse[i].loc];
DFS(cur+1);
result -= map[horse[i].road][horse[i].loc];
horse[i].loc = temploc;
horse[i].road = temproad;
}
}
else if(newloc == 15)
{
if(check(3,0,i))
{
horse[i].loc = 0;
horse[i].road = 3;
result += map[horse[i].road][horse[i].loc];
DFS(cur+1);
result -= map[horse[i].road][horse[i].loc];
horse[i].loc = temploc;
horse[i].road = temproad;
}
}
else if(newloc >= maplen[0])
{
horse[i].loc = maplen[0];
horse[i].arrived = true;
DFS(cur+1);
horse[i].arrived = false;
horse[i].loc = temploc;
}
else
{
if(check(0,newloc,i))
{
horse[i].loc = newloc;
result += map[horse[i].road][horse[i].loc];
DFS(cur+1);
result -= map[horse[i].road][horse[i].loc];
horse[i].loc = temploc;
}
}
}
else if(horse[i].road == 1)
{
if(newloc >= maplen[1])
{
horse[i].loc = maplen[1];
horse[i].arrived = true;
DFS(cur+1);
horse[i].arrived = false;
horse[i].loc = temploc;
}
else
{
if(check(1,newloc,i))
{
horse[i].loc = newloc;
result += map[horse[i].road][horse[i].loc];
DFS(cur+1);
result -= map[horse[i].road][horse[i].loc];
horse[i].loc = temploc;
}
}
}
else if(horse[i].road == 2)
{
if(newloc >= maplen[2])
{
horse[i].loc = maplen[2];
horse[i].arrived = true;
DFS(cur+1);
horse[i].arrived = false;
horse[i].loc = temploc;
}
else
{
if(check(2,newloc,i))
{
horse[i].loc = newloc;
result += map[horse[i].road][horse[i].loc];
DFS(cur+1);
result -= map[horse[i].road][horse[i].loc];
horse[i].loc = temploc;
}
}
}
else if(horse[i].road == 3)
{
if(newloc >= maplen[3])
{
horse[i].loc = maplen[3];
horse[i].arrived = true;
DFS(cur+1);
horse[i].arrived = false;
horse[i].loc = temploc;
}
else
{
if(check(3,newloc,i))
{
horse[i].loc = newloc;
result += map[horse[i].road][horse[i].loc];
DFS(cur+1);
result -= map[horse[i].road][horse[i].loc];
horse[i].loc = temploc;
}
}
}
}
}
}
int main(void)
{
for(int i = 0; i < 5; i++)
{
horse[i] = {0,0,0};
}
for(int i = 0; i <10; i++)
{
cin >> dice[i];
}
DFS(0);
cout << maxa << endl;
}'Algorithm' 카테고리의 다른 글
| 백준 17070번 파이프 옮기기 1 (삼성 A형) (0) | 2020.03.02 |
|---|---|
| 백준 16637번 괄호 추가하기 (삼성 A형) (0) | 2020.03.01 |
| 백준 17822번 원판 돌리기 (삼성 기출) (0) | 2020.02.28 |
| 백준 5373번 큐빙 (삼성 기출) (0) | 2020.02.26 |
| 백준 15685번 드래곤 커브 (삼성 기출) (0) | 2020.02.25 |
