[백준 17825][C++] 주사위 윷놀이

문제

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

17825번: 주사위 윷놀이

본 문제에 대한 풀이는 아래의 블로그를 참고하여 구현했다. 해당 문제를 각 경로를 나누어 풀어 어렵게 구현하다 실패한 뒤, 여러 풀이를 찾아보았다. 그중 가장 코드가 깔끔하고 이해하기 쉬웠고 하드코딩에 대한 나의 생각도 바꿔놓았다.

[참고 링크 : 안산 학생의 찬란한 개발 블로그]

 

풀이 과정

1. 윷놀이 판의 이동 순서, 각 칸의 점수, 방향 전환 구간을 기록한다. (하드 코딩)

2. DFS를 통해 윷판의 말을 이동시키는 과정의 모든 경우를 탐색하며 최대 값을 구한 뒤, 출력한다.

 

세부 풀이

(1)

윷놀이 말의 진행 순서, 각 칸의 점수, 방향 전환 위치, 현재 칸에 말이 있는지 여부를 하드코딩 형식으로 기록한다. 문제에서 주어진 윷놀이 판은 변하지 않으며, 마땅한 규칙이 존재하지 않는다. 따라서 오히려 하드 코딩을 통한 풀이가 깔끔하고 간단하다. (소스코드의 주석 참고)

 

(2)

DFS방식으로 모든 경우를 탐색하며, 방문 전의 상태를 prev와 now로 기록한 뒤, DFS탐색을 마치고 원래대로 되돌리는 방식으로 구현했다.

 

 

소스 코드

#include <iostream>

using namespace std;


//윷놀이 판(순서)
int map[35];

//현재 칸에 말이 있는지 확인
bool is_filled[35];

//윳놀이 판의 각 칸의 점수
int score[35];

//방향을 바꿔야할 곳에 표시
int turn[35];

//주사위 10번
int dice[10];

//각 말의 위치 표시
int stone[4];

int ans=0;

void Input(){
    for(int i=0;i<21;i++) map[i]=i+1;
    map[21]=21;

    for(int i=22;i<27;i++) map[i]=i+1;
    map[28]=29; map[29]=30; map[30]=25;
    map[31]=32; map[32]=25; map[27]=20;

    turn[5]=22; turn[10]=31; turn[15]=28;
    turn[25]=26;

    for(int i=0;i<21;i++) score[i]=i*2;
    score[22]=13; score[23]=16; score[24]=19;
    score[31]=22; score[32]=24; score[28]=28;
    score[29]=27; score[30]=26; score[25]=25;
    score[26]=30; score[27]=35;


    for(int i=0;i<10;i++) cin >> dice[i];
}



void DFS(int cnt, int sum) {
    if (cnt==10) {
        if (sum > ans) ans = sum;
        return;
    }
    for (int i=0; i<4; i++) {
        // 현재 말 위치, 이동 할 말 위치
        int prev = stone[i];
        int now = prev;
        // 움직여야 하는 횟수
        int move = dice[cnt];
 
        // 만약 현재 위치가 방향 전환 해야하는 곳 이라면 방향 전환 후 이동거리 1 감소
        if (turn[now] > 0) {
            now = turn[now];
            move -= 1;
        }
        // 주사위 만큼 이동
        while (move--) {
            now = map[now];
        }
 
        //현재 위치가 끝이거나 이미 차있다면 DFS 진행하지 않는다.
        if (now != 21 && is_filled[now] == true) continue;

        //이동이 진행되어 prev 위치에 있던 말을 now 로 옮겼다.
        is_filled[prev] = false;
        is_filled[now] = true;
        stone[i] = now;
        
        DFS(cnt + 1, sum + score[now]);
 
        stone[i] = prev;
        is_filled[prev] = true;
        is_filled[now] = false;
    }
}



int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);

    Input();
    DFS(0,0);
    cout << ans << "\n";
    return 0;
}

 

결과 및 후기

해당 문제는 오히려 처음에 생각한 대로 각 부분들이 잘 구축되어 잘 풀었다고 생각이 들었었다. 하지만 테스트 케이스를 넣어본 결과 답이 애매하게 계속 달랐고 어딘가 놓치고 있는 부분이 있었던 것 같다. 각 경로를 나누어 판단하는 방식이었는데, 정말 많은 시간을 투자해도 어디서 오류가 발생하는지 찾기 어려웠다.

그 후 문제 풀이를 찾아보던 중 하드 코딩으로 구현한 코드를 보고 놀랐다. 이렇게 간결하고 깔끔하게 구현할 수 있구나...

왠지 모르게 마음 한구석으로 하드코딩은 멀리해야 한다는 생각을 가지고 있었는데, 이렇게 문제의 상황이 불변하고 마땅한 규칙이 없는 경우 강력한 풀이가 될 수 있다는 것을 절실히 느낄 수 있는 풀이였다.