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

[문제보기]

 

[해결과정]

 1. 윷놀이 판을 구현 (map 초기화/설정)

  -> 해당 노드에 다음 이동할 노드 번호를 저장 (map 배열)

  -> 방향 전환이 되는 노드를 따로 관리 (turn 배열)

  -> 각각의 노드의 점수를 관리 (score 배열)

  -> 해당 노드에 말이 있는지 없는지 확인 배열 (check 배열)

 

 

 2. 주사위는 무조건 10번 던지니까, 10번 횟수 기록 (arr 배열)

 

 3. 말은 총 4마리로 움직임

  -> 순열 구현 ( 각각의 주사위로 인하여 어떤 말을 움직일지 모르니 완전 탐색 DFS 구현)

 

 4. 말의 움직임

  -> 현재 말의 위치, 말이 도착할 위치, 주사위의 갯수 총 3개의 변수 필요

  -> 예외 처리 : 만약 현재 위치가 변환점이라면, turn 배열을 이용하여 위치 변환

                   : 만약 도착 위치에 다른 말이 있다면 continue;

 

[소스코드]

#include<iostream>
using namespace std;
 
// 주사위
int arr[10];
// 현재 말의 위치
int mal[4];
 
// 윷놀이 판
int map[35];
// - 판에서 방향 전환
int turn[35];
// - 현 위치에 말이 있는지 확인
bool check[35];
// - 윷놀이 판의 점수
int score[35];
 
// 최종 값
int ans = 0;
 
void dfs(int cnt, int sum) {
    if (cnt == 10) {
        //실행 할 곳
        if (sum > ans) ans = sum;
 
        return;
    }
    for (int i = 0; i < 4; i++) {
        // 현재 말 위치, 이동 할 말 위치
        int prev = mal[i];
        int now = prev;
        // 움직여야 하는 횟수
        int move = arr[cnt];
 
        // 만약 현재 위치가 방향 전환 해야하는 곳 이라면..
        if (turn[now] > 0) {
            now = turn[now];
            move -= 1;
        }
        // 주사위 만큼 이동
        while (move--) {
            now = map[now];
        }
 
        if (now != 21 && check[now] == true) continue;
 
        check[prev] = false;
        check[now] = true;
        mal[i] = now;
        
        dfs(cnt + 1, sum + score[now]);
 
        mal[i] = prev;
        check[prev] = true;
        check[now] = false;
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
 
    // 맵 초기화
    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 >> arr[i];
 
    dfs(0, 0);
 
    cout << ans << "\n";
 
 
    return 0;
}

 

[해결 과정 중 실수한 부분]

 처음에 설계할 때 굉장히 쉽게 느껴져서, 신나게 하드 코딩을 했다. 하지만 결과는 터무니 없었다. 다만, 테스트케이스중 1개는 맞았다;;... 

 

 이후 단톡방에서 질문을 했는데, 도저히 디버깅이 되지않아, 새로이 코드를 작성했다. 참고 한 코드를 이용했더니 코드의 2/3 정도가 단축되었다. 또한 이해도 쉬웠고, 가독성도 좋았으며.. 해결도 빠르게 되었다..

 

 2019 삼성 하반기 역량 테스트 오후 문제인데, 풀고 나니 굉장히 쉬워보인다;;...ㅠㅠㅠ

 

[관련 문제 혹은 비슷한 문제]

 X