17825. 주사위 윷놀이

문제 링크

17825번: 주사위 윷놀이 (acmicpc.net)

 

풀이

윷놀이의 말판을 어떻게 구현하느냐는 사람에 따라 갈리겠지만, 필자는 2차원 배열로 다음과 같이 구현하였다.

배열 범위를 벗어나면 도착한 것으로 취급하면 되므로, 도착 칸은 구현하지 않았다.

 

이런 식으로 말판을 짜고, 말 4개를 10턴 동안 움직일 순서를 정해서, 그 순서에 따라 윷놀이를 실행하여 점수를 리턴하는 함수 move를 구현한다. 이때, 말을 움직이는 경우의 수는 4¹⁰가지가 되어야 할 것 같지만, 4⁹가지만 생각해도 된다. 왜냐하면 말이 어떤 것인지에 따라 점수가 달라지는 것이 아니기 때문이다. 쉽게 말해 1번째 말을 10번 움직이든, 2번째 말을 10번 움직이든 점수는 똑같으므로, 1턴째에 움직일 말을 정하는 것은 의미없다는 것이다. 사실 여기서 좀 더 생각하면 순서가 1111122222인 것과 2222233333인 것도 사실상 똑같으니 이 부분도 줄이는 게 좋겠지만, 이 정도로도 AC를 받았고, 필자의 구현 능력의 한계로 넘어가기로 한다.

 

문제에서 시작과 도착 칸을 제외한 칸에 말은 하나씩만 존재해야 하고, 이미 도착한 말은 더 이상 움직일 수 없다고 하였다. 만약 한 칸에 두 개 이상의 말이 존재해야 하거나, 도착한 말을 계속 움직이려 한다면 move에서 예외값을 리턴하고 함수를 종료하도록 하면 된다. 그래도 되냐고 할 수 있겠지만, 그건 그냥 문제에 어긋난 상황이 발생해서 점수 획득에 실패한 세계선이라고 생각하면 된다. 어긋나지 않고 무사히 모든 점수 획득에 성공한 세계선은 달리 존재하니 걱정 말자.

 

문제를 처음 풀게 되면 갈림길을 처리하는 것이 난감하게 느껴질 것이다. 그런데 주사위 숫자에 따른 말판 위에서 말의 위치 변화를 주의깊게 생각해 본다면 구현하는 건 크게 어렵지 않을 것이라 생각한다. 참고로 필자는 2번 틀리고 통과했는데, 처음에는 말판의 점수가 전부 다르다고 착각해서 그 값을 key처럼 써먹으려다 틀렸고, 두 번째는 갈림길 통과할 때 위치계산을 잘못해서 틀렸다. 이 문제는 틀리면 디버깅도 쉽지 않으니 주의깊게 풀도록 하자.

 

시간 복잡도

이 코드의 중점은 move의 호출 횟수로, chooseAndMove 함수로 2~10턴 동안 움직일 말의 순서를 정한 뒤 move 함수를 호출하여 점수를 계산한다. 4개의 말이 9회의 턴 동안 움직이는 순서의 경우의 수는 4⁹ = move의 호출 횟수로, 시간 복잡도는 \(O(4^9)\)이다.

 

소스코드

#include <iostream>
#include <algorithm>
#include <utility>
#define X first
#define Y second
#define DEST0    20
#define DEST1    3
#define DEST2    6
using namespace std;

int ans;
int dice[10];
int order[10];
pair<int, int> pawn[4];
bool finished[4];
bool occupied[4][20];
int board[4][20] = { {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, 25, 30, 35, 40},
                 {28, 27, 26} };

void initState() {
    fill(finished, finished + 4, false);
    for (int i = 0; i < 4; i++) {
        fill(occupied[i], occupied[i] + 20, false);
    }
    fill(pawn, pawn + 4, make_pair(0, 0));
}

int move() {
    int score = 0;
    for (int i = 0; i < 10; i++) {
        int curPawn = order[i];
        if (finished[curPawn]) return -1;
        pair<int, int> src = pawn[curPawn];
        occupied[src.X][src.Y] = false;

        if (src.X == 0 && src.Y == 5) {
            src.X = 1;
            src.Y = -1;
        }
        else if (src.X == 0 && src.Y == 10) {
            src.X = 2;
            src.Y = -1;
        }
        else if (src.X == 0 && src.Y == 15) {
            src.X = 3;
            src.Y = -1;
        }

        int destX = src.X;
        int destY = src.Y + dice[i];

        if (destX == 0 && destY >= DEST0) {
            destX = 2;
            destY -= 15;
        }
        else if ((destX == 1 || destX == 3) && destY >= DEST1) {
            destX = 2;
            destY -= 1;
        }

        if (destX == 2 && destY >= DEST2) {
            finished[curPawn] = true;
            continue;
        }

        if (occupied[destX][destY]) return -1;
        occupied[destX][destY] = true;
        score += board[destX][destY];
        pawn[curPawn] = { destX, destY };
    }

    return score;
}

// 10턴 동안 움직일 말의 순서를 백트래킹으로 뽑는 함수
void chooseAndMove(int cnt) {
    if (cnt == 10) {
        initState();
        int result = move();
        if (result != -1) ans = max(ans, result);
        return;
    }

    for (int i = 0; i < 4; i++) {
        order[cnt] = i;
        chooseAndMove(cnt + 1);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    for (int i = 0; i < 10; i++) cin >> dice[i];
    chooseAndMove(1);
    cout << ans;
    return 0;
}