[백준] 17825. 주사위 윷놀이

문제

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

풀이

개인적으로 정말 힘들었던 문제였다. 확실히 시뮬레이션 유형에 많이 약한 것 같다. (구현력이 너무 안 좋다. 언제 쯤 실수 없이 완벽하게 만들 수 있을지..)

맵도 다 주어져 있고, 조건도 별로 까다로워 보이지 않아서 쉽다고 생각했는데, 그렇게 이틀 3시간씩 6시간 동안 못 풀고 있었다. 엄청난 생각의 오류와 실수가 뒤섞여서 날 정말 힘들게 만들었다..
일단 링크를 통해서 볼 수도 있지만, 맵은 아래와 같이 생겼다.

일단 맵부터 설명이 친절하지 않다. 파란색 칸에서 시작하면 파란 화살표를 따라 간다고 했는데, 그럼 파란 화살표를 따라가다가 쭉 직진하는건지, 중간에 빨간 화살표를 만나서 올라가는건지 명확하지가 않다.
결론부터 말하자면, 10, 20, 30에서 출발하는 경로는 아래와 같다.

문제에서 무조건 화살표를 따라간다고 나와 있기 때문에 그냥 쭉 가다가 빨간 화살표를 만나 위로 올라가는 방식이다. 오른쪽과 아래쪽에서 시작하는 것도 마찬가지다.

그렇다면 어떻게 풀어야 할까? 직관적으로는

시작부터 38까지 10, 20, 30을 안 거치고 쭉 가는 루트
10에서 출발하는 루트
20에서 출발하는 루트
30에서 출발하는 루트

를 따로 구해주면 된다고 생각할 수 있다. 여기서부터 문제가 발생하는데, 10, 20, 30에서 시작하는 루트를 각각 다른 배열로 만들어준다면 공통된 부분인 25, 30, 35, 40 루트가 어떤 루트를 통해서 접근을 했는지 확인을 하기 힘들다. 즉 10 루트 배열에선 35 위치에 말이 있다고 나왔다면, 20, 30루트에서도 35위치에 말이 있다고 계속 동기화를 해줘야한다.

따라서 10 ~ 25까지 가는 배열(왼쪽 루트), 20 ~ 25까지 가는 배열(아래쪽 루트), 30 ~ 25까지 가는 배열(오른쪽 루트), 25 ~ 40까지 가는 배열(최종 루트)를 따로 찢어서 만들어줬다.

두번째 문제는 움직이는 방식을 그냥 주사위의 숫자만큼 한번에 이동시켰는데 , 이런 식으로 만든다면 각 위치에서 이게 최종 루트에 들어온건지, 그냥 끝점에 가서 끝난건지, 최종 루트 어딘가에서 시작해서 끝났는지를 전부 구해줘야한다.

따라서 그냥 1칸씩 이동하면서 각각 루트의 배열의 끝점에 도달했을 때 전부 최종 루트의 시작점이 되게 만들어 줬다.

마지막 문제는 이상하게 테스트 케이스 3이 항상 218로 나온다는 것이었는데, 문제를 잘 생각해보자. 끝점의 바로 뒤의 위치인 40은 최종루트를 통해서 갈 수도 있지만, 지름길이 아닌 외곽 루트를 완전히 뺑 돌아가는 루트도 40을 거치게 된다. 따라서 이 경우도 외곽 루트를 도는게 끝점에 도달했으면, 최종 루트의 맨 마지막 지점으로 이동하게 해서 외곽 루트와 최종 루트가 별개의 길인 것 마냥 인식하는 것을 없애주었다.

루트를 결정하는 문제는 위와 같은데, 어떤 말을 어떻게 움직일지를 정하는 것은 어떻게 할까?

일단 문제는 합의 최댓값을 구하는 것이므로 여러가지의 경우의 수가 나온다는 의미가 되며, 이것은 DFS를 통해 경우의 수를 모두 구해보라는 말이라고 추측할 수 있다. 즉, 10번의 주사위 굴리기에 1번 말인 경우, 2번 말인 경우, 3번 말인 경우, 4번 말인 경우를 모두 넣어서 계산해보면 되겠다. 이렇게 하면 4^10 의 경우의 수가 나오므로 1초면 충분히 통과할 수 있다. 따라서 DFS로 다 돌아보면 되겠다.

코드를 통해서 더 자세히 보도록 하자.

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

using namespace std;

int map[71], ismap[71];
pair<int, int> h[4];
int order[10], answer;

// 루트를 찾는 함수이다.
// 10에서 시작하는 루트는 31 ~ 33 (왼쪽 루트)
// 20에서 시작하는 루트는 41 ~ 42 (아래쪽 루트)
// 30에서 시작하는 루트는 51 ~ 53 (오른쪽 루트)
// 25에서 시작하는 루트는 61 ~ 64 (최종 루트)
// 0에서 시작하는 루트는 1 ~ 20 (외곽 루트)
// 이렇게 나눠 준 이유는, 각각의 배열로 나눠버리면 동기화를 해줄 수 없기 때문에 특정 루트의 끝점에 도달했으면, 연결 된 다음 루트의 시작점에 도달했다는 것으로 표현하도록 했다.
int find(int ismap[], int dice, int i, pair<int, int> horse[]){
    // pos는 말의 현재 위치
    int pos = horse[i].first;
    // tpos는 이동하고자 하는 위치를 저장하기 위함. 시작은 pos에서 시작해서 dice 만큼 1씩 이동할 것이다.
    int tpos = pos;
    // 이 때, 현재 시작 위치가 5이면, tpos를 30에서 시작한다고 가정하자 (10에서 시작하는 루트는 배열 인덱스 31, 32, 33에 저장되어 있으므로)
    if(pos == 5) tpos = 30;
    // 10, 15에 대해서도 각각 저장해주자.
    else if(pos == 10) tpos = 40;
    else if(pos == 15) tpos = 50;
    
    for(int j = 0; j < dice; j++){
        // tpos를 1씩 증가하면서 (말이 한 칸씩 이동함)
        tpos++;
        // 만약 현재 지점이 10, 20, 30 루트의 각각의 끝점일 경우, (어차피 모든 루트의 인덱스는 숫자가 겹치는 일이 없이 다 따로 떨어져있으므로 이렇게 한꺼번에 체크해도 문제 없음)
        if(tpos == 34 || tpos == 43 || tpos == 54){
            // 최종루트의 시작 지점으로 진입한다.
            tpos = 61;
        }
        // 만약 현재 지점이 외곽 루트의 끝점인 경우 최종 루트의 마지막 점으로 이동한다. (그림에서 38 다음에 40 (최종 루트 끝지점) 이므로)
        else if(tpos == 20) tpos = 64;
        
        
        // 이렇게 배열을 따로 나눠서 각 지점으로 진입하게끔 설정하는 것은 해당 위치에 말이 있는지 확인하는 동기화를 위해서다.
    }
    
    //cout << "horse : " << i << " horse pos : " << pos << " dice :  " << dice << " horse next pos : "  << tpos <<'\n';
    
    // 만약 이동하고자 하는 위치가 64가 넘어가면 = 최종 루트의 끝점을 넘어가면 = 말이 도착점에 도착했다면
    if(tpos > 64){
        // 도착점인 인덱스 70으로 보내버리고 말이 있던 위치는 0으로 만들어준다. (참고로 horse[i].second는 말이 움직였는지 아닌지를 판단하는 값이다.)
        horse[i].first = 70; horse[i].second = 0; ismap[pos] = 0; return 0;
    }
    // 64를 안 넘었으면 = 맵 내부 어딘가에 아직 있다면
    else if(tpos <= 64){
        // 다음 위치에 다른 말이 존재하지 않는다면,
        if(ismap[tpos] == 0){
            // 그 지점으로 이동하고 현재 위치는 말이 없음으로 바꿔준다.
            horse[i].first = tpos; horse[i].second = 0; ismap[pos] = 0; ismap[tpos] = 1; return map[tpos];
        }
        // 다음 위치에 다른 말이 존재한다면
        else if(ismap[tpos] == 1){
            // 움직일 수 없음으로 변환해준다.
            horse[i].second = 1; return 0;
        }
    }
    return 0;
}

void DFS(int idx, int ismap[], pair<int, int> horse[4], int total){
    
    // 10회가 넘어가면 크기 비교 후 끝낸다.
    if(idx >= 10){
        answer = max(answer, total);
        return;
    }
    
    int tmap[71]; pair<int, int> th[4];
    for(int i = 0; i < 71; i++){
        tmap[i] = ismap[i];
    }
    for(int i = 0; i < 4; i++){
        th[i] = horse[i];
    }
    // 말 4개를 모두 각 순서에 대입해준다.
    for(int i = 0; i < 4; i++){
        // 만약 현재 말이 이미 도착점에 도착한 경우는 사용하지 않는다.
        if(horse[i].first != 70){
            // find함수로 이 말이 도착한 위치의 점수를 가져온다.
            int sum = find(tmap, order[idx], i, th);
            // 이 말이 움직였다면 DFS를 다시 돌려준다.
            if(th[i].second == 0){
                DFS(idx + 1, tmap, th, total + sum);
                
                for(int i = 0; i < 71; i++){
                    tmap[i] = ismap[i];
                }
                for(int i = 0; i < 4; i++){
                    th[i] = horse[i];
                }
            }
        }
    }
}

int main(){
    
    for(int i = 0; i < 10; i++){
        cin >> order[i];
    }
    
    for(int i = 1; i <= 20; i++){
        map[i] = i * 2;
    }
    map[31] = 13; map[32] = 16; map[33] = 19;
    map[41] = 22; map[42] = 24;
    map[51] = 28; map[52] = 27; map[53] = 26;
    map[61] = 25; map[62] = 30; map[63] = 35; map[64] = 40;
    
    DFS(0, ismap, h, 0);
    cout << answer;
    return 0;
}

Cat On The Keyboard

이 블로그 검색

[백준] 17825. 주사위 윷놀이

댓글

댓글 쓰기