백준 17825 - 주사위 윷놀이

문제 : https://www.acmicpc.net/problem/17825

문제 요약

1. 시작 칸에 말 4개가 위치한다.

2. 말을 하나씩 선택하여 화살표 방향대로 움직이며, 파란색 지점에 도달하면 경로를 변경한다.

3. 총 10번 움직이며 1~5 칸 까지 랜덤으로 움직일 수 있다.

3-1. 단, 이동한 곳에 이미 다른 말이 존재하면 이동할 수 없다. (도착점은 예외) 

4. 말이 이동할때마다 칸에 적힌 점수가 추가되며 최댓값을 구해보자.

 

풀이 과정

해당 문제는 구현 + DFS를 통해 모든 경우의 수를 탐색하여 해결했다.

각 파란색 지점은 이동 경로가 변경되는 변곡점으로, 윷놀이 배열에서 따로 저장한다.

 

단, 25,30,35,40,도착 구간은 이동 경로가 변경되더라도 겹치는 구간이기 때문에, 해당 칸에 말이 존재하는지 판별하기 어렵다. 

따라서 해당 구간 역시 배열에서 따로 저장하여 관리하였다.

 

int scores[5][23] = {
    {0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38},
    {10,13,16,19},
    {20,22,24},
    {30,28,27,26},
    {25,30,35,40,0}
};

 

 

 

도착 위치에 다른 말이 존재하는지 판별하기 위해 각 말의 위치를 배열에 저장하여 관리한다.

 

// 말 : 0 ~ 3번
typedef struct option {
    int y,x;
}op;
deque < op > horses; // 말 위치데이터 저장

...

// 도착 위치에 다른말이 있다면 패스 (도착점 제외)
if(scores[nexty][nextx] != 0) {
    for(int j=0; j<4; j++) {
        if(i != j && (horses[j].y == nexty && horses[j].x == nextx)) {
            flag = true;
            break;
        }
    }
}

 

 

이제 각 구간을 배열에 나눠 저장하였으니, 변곡점에 도달했을 경우 또는 범위를 벗어났을 경우 알맞게 위치를 조정해주면 된다.

 

        // 변곡점
        if(nexty == 0 && nextx == 5) {
            nexty = 1, nextx = 0;
        }
        else if(nexty == 0 && nextx == 10) {
            nexty = 2, nextx = 0;
        }
        else if(nexty == 0 && nextx == 15) {
            nexty = 3, nextx = 0;
        }
        
        // 25,30,35,40 구간 변곡점
        else if(nexty == 1 && nextx >= 4) {
            nexty = 4, nextx -= 4;
        }
        else if(nexty == 2 && nextx >= 3) {
            nexty = 4, nextx -= 3;
        }
        else if(nexty == 3 && nextx >= 4) {
            nexty = 4, nextx -= 4;
        }
        else if(nexty == 0 && nextx == 20) {
            nexty = 4, nextx = 3;
        }

        // 도착
        else if(nexty == 0 && nextx > 20) {
            nexty = 4, nextx = 4;
        }
        else if(nexty == 4 && nextx >= 5) {
            nexty = 4, nextx = 4;
        }

 

마지막으로 DFS 재귀호출을 통해 점수를 더해나가며, 최대값을 구한다.

재귀호출 후 원본 값을 복원시켜야 하는 점을 주의하자.

 

        horses[i].y = nexty;
        horses[i].x = nextx;
        solution(moveIdx+1, sum+scores[nexty][nextx]);
        horses[i].y = nowy;
        horses[i].x = nowx;

 

 

전체 코드

#include <iostream>
#include <stdio.h>
#include <deque>

using namespace std;

int scores[5][23] = {
    {0,2,4,6,8,10,12,14,16,18,20,22,24,26,28,30,32,34,36,38},
    {10,13,16,19},
    {20,22,24},
    {30,28,27,26},
    {25,30,35,40,0}
};
int diceNum[10];

// 말 : 0 ~ 3번
typedef struct option {
    int y,x;
}op;
deque < op > horses; // 말 위치데이터 저장

int answer = 0;

void solution(int moveIdx, int sum) {
    // 10번 이동 시 종료
    if(moveIdx == 10) {
        answer = (answer > sum) ? answer : sum;
        return;
    }
    int nowy,nowx;
    int nexty, nextx;
    int dice = diceNum[moveIdx];
    bool flag;
    for(int i=0; i<4; i++) {
        nowy = horses[i].y;
        nowx = horses[i].x;
        nexty = horses[i].y;
        nextx = horses[i].x;
        // 도착한 말은 패스
        if(nowy == 4 && nowx == 4) continue;
        // 이동시키기
        nextx += dice;
        flag = false;

        // 변곡점
        if(nexty == 0 && nextx == 5) {
            nexty = 1, nextx = 0;
        }
        else if(nexty == 0 && nextx == 10) {
            nexty = 2, nextx = 0;
        }
        else if(nexty == 0 && nextx == 15) {
            nexty = 3, nextx = 0;
        }
        
        // 25,30,35,40 구간 변곡점
        else if(nexty == 1 && nextx >= 4) {
            nexty = 4, nextx -= 4;
        }
        else if(nexty == 2 && nextx >= 3) {
            nexty = 4, nextx -= 3;
        }
        else if(nexty == 3 && nextx >= 4) {
            nexty = 4, nextx -= 4;
        }
        else if(nexty == 0 && nextx == 20) {
            nexty = 4, nextx = 3;
        }

        // 도착
        else if(nexty == 0 && nextx > 20) {
            nexty = 4, nextx = 4;
        }
        else if(nexty == 4 && nextx >= 5) {
            nexty = 4, nextx = 4;
        }

        // 도착 위치에 다른말이 있다면 패스 (도착점 제외)
        if(scores[nexty][nextx] != 0) {
            for(int j=0; j<4; j++) {
                if(i != j && (horses[j].y == nexty && horses[j].x == nextx)) {
                    flag = true;
                    break;
                }
            }
        }
        if(flag) continue;

        horses[i].y = nexty;
        horses[i].x = nextx;
        solution(moveIdx+1, sum+scores[nexty][nextx]);
        horses[i].y = nowy;
        horses[i].x = nowx;
    }
}

int main() {
    int num;
    horses.push_back({0,0});
    horses.push_back({0,0});
    horses.push_back({0,0});
    horses.push_back({0,0});

    for(int i=0; i<10; i++) {
        scanf("%d",&diceNum[i]);
    }
    solution(0,0);
    printf("%d\n",answer);
}